숫자 n(주사위 개수), 면의 개수(faces), 그리고 목표 합계(total)가 주어졌다고 가정해 봅시다. 이때 각각 faces개의 면을 가진 n개의 주사위를 던져 그 합이 정확히 total이 되도록 만들 수 있는 경우의 수를 구해야 합니다. 결과값이 매우 커질 수 있으므로 10**9 + 7로 나눈 나머지를 반환하면 됩니다.
예를 들어 입력이 n = 2, faces = 6, total = 8이라면 출력은 5가 됩니다. 두 개의 6면체 주사위로 8을 만드는 방법은 다음과 같이 5가지이기 때문입니다: (2와 6), (6과 2), (3과 5), (5와 3), (4와 4).
이 문제는 동적 계획법(DP)을 활용하면 효율적으로 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.
m := 10^9 + 7
dp := 크기가 (total + 1)인 리스트를 생성하고 모든 값을 0으로 초기화
face를 1부터 min(faces, total)까지 반복하면서 dp[face] := 1로 설정 (주사위 하나만 던졌을 때 해당 눈금이 곧 합계가 되므로)
i를 0부터 n - 2까지 반복:
j를 total부터 0까지 1씩 감소시키며 반복
dp[j] := j - f >= 1을 만족하는 모든 f(1부터 faces까지)에 대한 dp[j - f] 값들의 합
dp 리스트의 마지막 원소를 m으로 나눈 나머지를 반환
핵심 아이디어는 1차원 DP 배열을 반복적으로 갱신하면서 주사위를 하나씩 추가해 가는 것입니다. 이렇게 하면 각 단계에서 '현재까지 고려한 주사위 개수'로 특정 합계를 만들 수 있는 방법의 수를 누적 계산할 수 있습니다. 아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution: def solve(self, n, faces, total): m = 10 ** 9 + 7 dp = [0] * (total + 1) for face in range(1, min(faces, total) + 1): dp[face] = 1 for i in range(n - 1): for j in range(total, 0, -1): dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1) return dp[-1] % m ob = Solution() n = 2 faces = 6 total = 8 print(ob.solve(n, faces, total))
입력
2,6,8
출력
5
이 알고리즘의 시간 복잡도는 O(n × total × faces)이며, 공간 복잡도는 O(total)입니다. 2차원 DP 테이블 대신 1차원 배열을 뒤에서부터 갱신하며 재활용하기 때문에 메모리 사용량을 효율적으로 줄일 수 있다는 점이 특징입니다.