[Python] 2758번 로또

 

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

2758번: 로또

---

 

23/03/13

 

 

전형적인 2차원 DP문제로, 만약 DP가 아니라 백트래킹으로 접근한다면 시간초과가 날 수도 있을 문제이다.

---

 

문제 접근 방식:

 

 

$\mathrm{DP}$문제를 접근할 때에는 먼저 상태를 정의하는게 우선이다.

 

이 문제에서는 영향을 미치는 요소가 $n$과 $m$ 두가지 라는 사실을 알 수 있다.

 

때문에 다음과 같이 상태를 정의해보자.

 

$\mathrm{DP}[i][j]$ $=$ 선영이가 지금까지 $i$개의 숫자를 골랐을 때, 숫자 $j$를 고르는 경우의 수

 

다음과 같이 상태를 정의한다면, 점화식을 세우는 것은 그리 어렵지는 않다.

 

 

문제에 주어진 바에 따르면, 선영이는 이전의 숫자보다 항상 적어도 2배가 크게끔 다음 숫자를 고른다고 하였다.

 

이를 이용하면, 선영이가 만약 이번에 $j$라는 숫자를 고르려고 한다면, 그 상태는 분명 이전 상태의 숫자보다 $2$배 이상이 되야하므로, 이전 상태의 숫자는 $0$부터 $j//2$까지 가능하다.

 

따라서 점화식은 아래와 같이 세울 수 있다.

 

$$\mathrm{DP}[i][j] = \mathrm{DP}[i-1][0] + ... + \mathrm{DP}[i-1][j//2]$$

 

 

초기 DP의 값($\mathrm{DP}[0][0]$)은 상태를 해석하자면, 아무것도 없는 상태, 한 가지로 해석할 수 있으므로 1이라고 초기화 해준다.

 

이후 숫자 제한 범위인 $n = 10$과 $m = 2000$까지의 $\mathrm{DP}$배열을 선언해주고, 이를 미리 채워줘서 각 쿼리마다 $\sum_{k = 0}^{m} \mathrm{DP}[n][k]$을 반환하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2758번 로또
# DP
'''
접근 방법:
DP[i][j] = 선영이가 지금까지 i개의 숫자를 골랐을 때, 숫자 j를 고르는 경우의 수
DP[i][j] = DP[i-1][1] + DP[i-1][2] + ... DP[i-1][j//2]
'''
DP = [[0 for _ in range(2001)] for _ in range(11)]
DP[0][0] = 1
for i in range(1, 11):
    for j in range(1, 2001):
        DP[i][j] = sum(DP[i-1][k] for k in range(j//2+1))
T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    print(sum(DP[n][k] for k in range(2**(n-1), m+1)))