문제 개요
d개의 주사위가 있고, 각 주사위는 1부터 f까지의 숫자가 적힌 면을 가지고 있다고 가정해 보겠습니다. 이때 주사위를 굴려서 윗면에 나온 숫자들의 합이 목표값(target)과 일치하도록 만드는 경우의 수를 전체 경우의 수(f^d) 가운데서 구하고, 그 결과를 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 d = 2, f = 6, target = 7이 입력으로 주어진다면 출력은 6이 됩니다. 6면체 주사위 두 개를 던져 합이 7이 되는 조합은 1+6, 2+5, 3+4, 4+3, 5+2, 6+1로 총 6가지이기 때문입니다.
해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 단계마다 'i번째 주사위까지 사용했을 때 합이 j가 되는 경우의 수'를 누적해 나가는 방식입니다. 단계별 과정은 다음과 같습니다.
- 모듈로 값 m := 10^9 + 7로 설정합니다.
- d × (t + 1) 크기의 DP 테이블을 생성하고 모든 값을 0으로 초기화합니다.
- i를 0부터 d − 1까지 반복하고, 내부에서 j를 0부터 t까지 반복합니다.
- i = 0인 경우(주사위 한 개만 사용): j가 1 이상 f 이하일 때만 dp[i][j] = 1이고, 그 외에는 0입니다.
- 그 외의 경우: l을 1부터 f까지 반복하면서 j − l > 0이면 dp[i][j] += dp[i−1][j−l]을 수행하고, 매번 결과를 m으로 나눈 나머지로 갱신합니다.
- 최종적으로 dp[d − 1][t]를 m으로 나눈 나머지를 반환합니다.
Python 구현 예시
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def numRollsToTarget(self, d, f, t):
mod = 1000000000+7
dp =[[0 for i in range(t+1)] for j in range(d)]
for i in range(d):
for j in range(t+1):
if i == 0:
dp[i][j] = 1 if j>=1 and j<=f else 0
else:
for l in range(1,f+1):
if j-l>0:
dp[i][j]+=dp[i-1][j-l]
dp[i][j]%=mod
return dp [d-1][t] % mod
ob = Solution()
print(ob.numRollsToTarget(2,6,7))입력
2 6 7
출력
6