다이나믹 프로그래밍 - 여러 번 주사위 굴려서 정해진 숫자 맞추기
처음엔 Coin Change 2 복붙하면 된다고 생각했는데, Wrong Answer를 3번 받고 나서야 '정확히 n개를 전부 써야 한다'는 결정적 차이를 깨달았습니다. 모듈로를 마지막에만 적용해 오버플로가 났던 경험, base case를 0으로 초기화해 결과가 전부 0이 되었던 삽질까지 함께 정리합니다.
Number of Dice Rolls With Target Sum (LeetCode 1155)
면이 k개인 주사위 n개를 굴려서 합이 target이 되는 경우의 수를 10^9 + 7로 나눈 나머지를 구하는 문제입니다.
이 문제를 처음 봤을 때 솔직한 심정은 “어? Coin Change 2랑 똑같은 거 아닌가?”였습니다. 실제로 그렇게 생각하고 Coin Change 2 코드를 거의 그대로 가져다 붙였는데, Wrong Answer가 세 번 연속으로 나왔습니다. 한참을 들여다보고 나서야 핵심적인 차이를 발견했습니다. Coin Change 2는 동전 개수에 제한이 없지만, 이 문제는 정확히 n개의 주사위를 전부 사용해야 합니다. 이 차이 하나 때문에 상태 정의가 완전히 달라지고, dp 테이블 채우는 방식도 달라집니다.
문제 설명 — 초등학생도 이해할 수 있게
여러분 앞에 면이 6개인 주사위가 2개 있습니다. (1, 2, 3, 4, 5, 6이 그려져 있죠.)
이 두 개를 굴려서 합이 7이 나오는 경우는 몇 가지일까요?
세어봅시다:
- 주사위 A=1, 주사위 B=6 → 합 7
- 주사위 A=2, 주사위 B=5 → 합 7
- 주사위 A=3, 주사위 B=4 → 합 7
- 주사위 A=4, 주사위 B=3 → 합 7
- 주사위 A=5, 주사위 B=2 → 합 7
- 주사위 A=6, 주사위 B=1 → 합 7
총 6가지입니다. 여기서 중요한 포인트 하나: (1, 6)과 (6, 1)은 다른 경우라는 겁니다. 주사위가 똑같이 생겼어도, 어떤 주사위에서 어떤 숫자가 나왔는지가 중요합니다.
이제 일반화하면: 면이 k개인 주사위 n개의 합이 target이 되는 경우의 수를 구하는 문제입니다. 단, 답이 너무 커질 수 있으니 10^9 + 7로 나눈 나머지를 반환합니다.
”브루트포스로 하면 왜 안 돼요?” — 저도 처음엔 이렇게 생각했습니다
솔직히 말해서, 저도 처음엔 “모든 경우를 다 세면 되지 않나?”라고 생각했습니다. 주사위 n개, 각각 k개의 선택지 → k^n 가지니까… n=30, k=30이면 30^30입니다.
이 숫자가 얼마나 큰지 체감이 안 되시는 분들을 위해: 우주에 존재하는 원자의 개수보다 훨씬 큽니다. 당연히 TLE(Time Limit Exceeded)가 납니다.
그래도 브루트포스에서 시작하는 건 좋은 접근입니다
“완전 탐색으로는 안 된다”는 걸 확인하는 것 자체가 DP로 넘어가는 첫걸음입니다. 재귀로 상태 공간 트리를 그려보면 어디서 중복 계산이 발생하는지 눈에 들어옵니다.
(n=3, target=7)
/ | \
주사위1=1 / 주사위1=2 | ... \ 주사위1=k
/ | \
(n=2, target=6) (n=2, target=5) (n=2, target=7-k)
/ | \ / | \
(n=1,5) (n=1,4) ... (n=1,4) (n=1,3) ...보다시피 (n=1, target=4) 같은 상태가 여러 경로에서 등장합니다. 처음 주사위 하나를 고정하고 나면, 나머지 n-1개의 주사위로 target - 첫주사위값을 만드는 하위 문제가 되는 구조입니다.
패턴 발견 — 여기서부터가 진짜 시작
주사위 3개, 목표 합이 7이라고 생각해봅시다.
한 개의 주사위 값이 1이면 → 주사위 2개로 7-1=6 을 만들어야 한다. 한 개의 주사위 값이 2이면 → 주사위 2개로 7-2=5 를 만들어야 한다. 한 개의 주사위 값이 3이면 → 주사위 2개로 7-3=4 를 만들어야 한다. …
패턴이 보이시나요? dp[n][target] = dp[n-1][target-1] + dp[n-1][target-2] + ... + dp[n-1][target-k]
이걸 점화식으로 표현하면:
dp[i][j] = Σ (dp[i-1][j - face]) (face = 1, 2, ..., k)단, j - face >= 0 일 때만 유효합니다 (합이 음수가 될 수는 없으니까요).
제가 실제로 Wrong Answer를 받았던 실수 3가지
실수 1: Modulo를 마지막에만 적용
C++나 Java에서 int는 약 21억까지밖에 표현하지 못합니다. 중간 합산에서 이걸 넘겨버리면 오버플로가 발생해 음수로 래핑됩니다. 결과는 당연히 Wrong Answer입니다. 저도 이 실수로 처음 제출이 틀렸습니다.
매 덧셈마다
% MOD를 적용하세요. Python은 arbitrary precision 정수라 오버플로는 없지만, mod를 안 하면 숫자가 천문학적으로 커져서 메모리와 속도가 폭발합니다.
// 나쁜 예 — 마지막에 한 번만 적용
int sum = a + b + c + d;
return sum % MOD;
// 좋은 예 — 매 덧셈마다 적용
int sum = ((a + b) % MOD + c) % MOD;
sum = (sum + d) % MOD;
return sum;실수 2: Base Case — dp[0][0] = 1을 빼먹음
“주사위 0개로 합 0을 만드는 방법”은 1가지(아무것도 안 하는 것)입니다. 이걸 0으로 초기화하면 모든 값이 0으로 수렴하는 참사가 발생합니다. 실제로 이 실수를 했을 때 전체 결과가 0만 나와서 처음엔 루프 자체를 의심했습니다. 반대로 n > 0일 때 dp[n][0]은 말이 안 되니 0이어야 합니다.
실수 3: Pruning (가지치기) 없이 DP 돌리기
target < n (최소 합보다 작음) 또는 target > n*k (최대 합보다 큼)일 경우, 답은 무조건 0입니다. 이걸 확인하지 않고 DP 테이블을 채우면 불필요한 연산이 발생하고, k가 클 때 낭비가 심합니다. 루프 경계를 잘못 잡으면 실제로 달성 불가능한 합에 대해서도 계산을 시도하게 됩니다.
Top-Down (메모이제이션) — 직관적으로 접근하기
초보자에게 더 직관적인 Top-Down 방식부터 시작합시다. 재귀에 캐시를 붙이는 방식입니다.
from functools import lru_cache
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
# 가지치기: 불가능한 경우 즉시 0 반환
if target < n or target > n * k:
return 0
@lru_cache(maxsize=None)
def dp(i: int, j: int) -> int:
# base case
if i == 0:
return 1 if j == 0 else 0
total = 0
for face in range(1, k + 1):
if j - face >= 0:
total = (total + dp(i - 1, j - face)) % MOD
return total
return dp(n, target)Python에서 @lru_cache는 일반 dict 기반 메모이제이션보다 훨씬 빠릅니다. 직접 딕셔너리로 캐시를 구현했다가 TLE가 나서 lru_cache로 교체한 뒤 통과한 경험이 있습니다.
Bottom-Up (타뷸레이션) — 더 빠르고 면접에서 빛을 발하는 방식
메모이제이션으로 감을 잡았으면, 타뷸레이션으로 최적화합시다. 2D 테이블을 머릿속에 그려보세요.
dp[2][7] = 6 — 주사위 2개로 합 7이 되는 경우가 6가지. 위에서 직접 세어본 그 숫자입니다.
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
# 가지치기
if target < n or target > n * k:
return 0
dp = [[0] * (target + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(1, target + 1):
for face in range(1, k + 1):
if j - face >= 0:
dp[i][j] = (dp[i][j] + dp[i-1][j - face]) % MOD
return dp[n][target]시간 복잡도: O(n * target * k) — n≤30, k≤30, target≤1000이면 약 90만 연산으로 충분합니다.
공간 최적화 — Rolling Array로 O(target)까지 줄이기
dp[i][j]를 계산할 때 필요한 건 오직 dp[i-1][...] 뿐입니다. 즉, 직전 행만 기억하면 됩니다.
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
if target < n or target > n * k:
return 0
prev = [0] * (target + 1)
prev[0] = 1
for i in range(1, n + 1):
curr = [0] * (target + 1)
for j in range(1, target + 1):
for face in range(1, k + 1):
if j - face >= 0:
curr[j] = (curr[j] + prev[j - face]) % MOD
prev = curr
return prev[target]공간 복잡도가 O(n * target)에서 O(target)으로 줄었습니다. 면접관 앞에서 이 최적화까지 보여주면 분명히 플러스 점수입니다.
면접관이 보는 포인트 — 이걸 물어보면 어떻게 답해야 할까?
면접관이 이 문제를 내는 진짜 이유는 “Knapsack 패턴을 인식하는가”를 보기 위함입니다. 이 문제는 “정해진 타겟을 만드는 경우의 수를 구하라” 패턴의 대표 예시입니다.
면접관 앞에서 이렇게 말할 수 있다면 합격점입니다:
- "이 문제는 0/1 Knapsack의 변형입니다. 각 주사위가 하나의 아이템이고, 1~k 값을 선택합니다."
- "점화식은 dp[i][j] = Σ dp[i-1][j-face] 입니다."
- "중간 합산마다 mod를 적용해야 오버플로를 방지할 수 있습니다."
- "공간 최적화로 O(target)까지 줄일 수 있는데, rolling array를 사용합니다."
마무리
이 문제에서 제가 가장 오래 헤맸던 부분은 알고리즘 자체가 아니라 “Coin Change 2와 뭐가 다른가”였습니다. 정확히 n개를 써야 한다는 제약 때문에 상태 정의가 달라지고, base case도 달라집니다. 비슷해 보이는 문제라도 제약 조건 한 줄이 풀이를 완전히 바꾼다는 것, 그것이 이 문제가 면접에 자주 등장하는 이유이기도 합니다. Top-Down에서 시작해 Bottom-Up으로, 다시 공간 최적화까지 세 단계로 풀어보는 연습을 해보시길 권합니다.