[BOJ] #2758 로또 (Python, Dynamic Programming)

🌱 문제

2758번: 로또

https://www.acmicpc.net/problem/2758

 

🌱 풀이1 - 백트랙킹 풀이(시간 초과)

m개의 자연 수 중에서 n개를 고르는 문제라 당연히 백트랙킹이라고 생각하고 처음에는 백트랙킹으로 풀었습니다.

def backtracking(n, m, lotto):
    if len(lotto) == n - 1:
        global answer
        answer += (m - (lotto[-1] * 2) + 1)
        return
    for i in range(lotto[-1]*2, m + 1):
        tmp = i
        for j in range(n - len(lotto) - 1):
            tmp *= 2
            if tmp > m:
                return
        lotto.append(i)
        backtracking(n, m, lotto)
        lotto.pop()


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    answer = 0
    for i in range(1, m + 1):
        backtracking(n, m, [i])
    print(answer)

시간 초과가 떠서 어떻게든 시간 초과를 줄여보고자 다음과 같은 방법을 사용했습니다.

• 만약 현재 lotto에 담겨 있는 숫자 중 마지막 숫자로 두 배씩 늘렸을 때 m보다 커지면 끝까지 lotto를 만들 수 없다는 의미이므로 바로 return
• lotto가 n이 될 때까지 탐색하지 않고 n - 1이 될 때까지 탐색 (→ 이게 무슨 의미인지,, 멍청한 나..♡) (근데 결국 탐색이 아니라 count를 세는 방식으로 코드를 변경해야 한다는 사실을 이 코드를 작성하면서 깨달았습니다.)

결국 탐색이 아니라 만들 수 있는 로또의 개수를 저장해놓고 계산하는 식으로 풀어야 겠다고 생각하여 다이나믹 프로그래밍을 이용하여 풀이를 하였습니다.

 

🌱 풀이2 - 다이나믹 프로그래밍 풀이

이 문제에서는 DP 배열이 2차원이어야 합니다. 왜냐하면 dp[i][j]에 j이하의 자연수로 길이 i의 로또를 만드는 방법을 저장해야 하기 때문입니다.

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())

    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(m + 1):
        dp[1][i] = i

    for i in range(2, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = dp[i][j-1]+dp[i-1][j//2]
    print(dp[n][m])

• dp[i][j]에는 j이하의 자연수로 로또 숫자 i개를 고르는 경우의 수를 저장합니다.
• dp[i][j] = dp[i][j-1] + dp[i-1][j//2]로 구할 수 있습니다.

• 예를 들어, n=4이고, m=10인 경우를 생각해 보겠습니다. 10이하의 자연수로 문제에서 주어진 규칙대로 로또 번호 4개를 만드는 경우의 수를 생각해야 합니다. 즉, dp[4][10]을 구하면 됩니다.
  이때, dp[4][10]는 dp[3][5] + dp[4][9]로 계산될 수 있습니다. 왜냐하면 10이하의 자연수로 로또 번호 4개를 고르면 되므로 9이하의 자연수로 4개의 로또 번호를 고르는 경우가 포함되고, 5이하의 자연수로 3개를 골라놓은 경우에 5의 2배인 10을 추가로 넣어주면되기 때문입니다.

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 2758 로또

# DP 풀이
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())

    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(m + 1):
        dp[1][i] = i

    for i in range(2, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = dp[i][j-1]+dp[i-1][j//2]
    print(dp[n][m])

역시 DP문제는 점화식을 생각해내면 구현은 정말 쉬운데, 점화식을 생각해내는게 참 어려운 것 같습니다..🫠