다이나믹 프로그래밍 - 여러 번 주사위 굴려서 정해진 숫자 맞추기
제출 버튼 누르고 TLE 보신 분들 주목. 순수 재귀와 Coin Change 2 함정에서 벗어나, 브루트포스 → 메모이제이션 → 타뷸레이션까지 함께 올라가는 LeetCode 1155 완전 정복 가이드입니다.
Number of Dice Rolls With Target Sum (LeetCode 1155)
면이 k개인 주사위 n개를 굴려서 합이 target이 되는 경우의 수를 10^9 + 7로 나눈 나머지를 구하는 문제입니다.
제가 처음 이 문제를 봤을 때의 솔직한 심정은 “어? 그냥 조합 문제 아닌가?”였습니다. 그리고 실제로 Reddit r/leetcode에서도 “Coin Change 2랑 똑같은 거 아니에요?”라는 질문이 심심찮게 올라오더라고요. 결론부터 말하면, 아닙니다. Coin Change 2는 동전 개수에 제한이 없지만, 이 문제는 정확히 n개의 주사위를 전부 사용해야 합니다. 이 차이 하나 때문에 Wrong Answer가 쏟아지는 걸 실제로 LeetCode Discuss에서 수도 없이 봤습니다.
문제 설명 — 초등학생도 이해할 수 있게
여러분 앞에 면이 6개인 주사위가 2개 있습니다. (1, 2, 3, 4, 5, 6이 그려져 있죠.)
이 두 개를 굴려서 합이 7이 나오는 경우는 몇 가지일까요?
세어봅시다:
| 주사위 A | 주사위 B | 합 |
|---|---|---|
| 1 | 6 | 7 |
| 2 | 5 | 7 |
| 3 | 4 | 7 |
| 4 | 3 | 7 |
| 5 | 2 | 7 |
| 6 | 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)가 나고, 실제로 LeetCode GitHub Issue #18932에서 한 유저가 “brute force로 통과해야 하는 거 아닌가요?”라고 올렸다가 바로 반려된 사례도 있습니다.
그래도 브루트포스에서 시작하는 건 좋은 접근입니다
“완전 탐색으로는 안 된다”는 걸 확인하는 것 자체가 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) 같은 상태가 여러 경로에서 등장합니다. Reddit의 한 유저가 딱 이걸 깨닫고 한 말이 인상적이었습니다:
“아! 첫 번째 주사위를 하나 고정하고 나면, 나머지
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 일 때만 유효합니다 (합이 음수가 될 수는 없으니까요).
실전에서 사람들이 가장 많이 하는 실수 3가지
실수 1: Modulo를 마지막에만 적용
LeetCode Discuss에서 정말 자주 보이는 패턴입니다. 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으로 수렴하는 참사가 발생합니다. 반대로 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 기반 메모이제이션보다 2~3배 빠릅니다. StackOverflow 질문(69597327)에서도 이 차이로 고생한 사례가 올라와 있으니 참고하세요.
Bottom-Up (타뷸레이션) — 더 빠르고 면접에서 빛을 발하는 방식
메모이제이션으로 감을 잡았으면, 타뷸레이션으로 최적화합시다. 2D 테이블을 머릿속에 그려보세요.
| i＼j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | … |
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 패턴을 인식하는가”를 보기 위함입니다. LeetCode Discuss의 DP Patterns 가이드에서도 1155번이 “Given a target, find number of distinct ways to reach the target” 패턴의 대표 예시로 분류되어 있습니다.
면접관 앞에서 이렇게 말할 수 있다면 합격점입니다:
- “이 문제는 0/1 Knapsack의 변형입니다. 각 주사위가 하나의 아이템이고, 1~k 값을 ‘선택’합니다.”
- “점화식은
dp[i][j] = Σ dp[i-1][j-face]입니다.” - “중간 합산마다 mod를 적용해야 오버플로를 방지할 수 있습니다.”
- “공간 최적화로 O(target)까지 줄일 수 있는데, rolling array를 사용합니다.”
마무리 — 여러분의 TLE를 응원합니다
마지막으로, 이 글을 읽고 계신 분들 중에 “와, 나 아직도 DP 어렵다”라고 느끼신다면 — 그게 정상입니다. 바바라 오클리 교수가 Learn How to Learn에서 말했듯이, 뇌는 한 번 생각한 패턴을 반복해서 떠올립니다. 잘못된 접근을 먼저 익히면, 나중에 다시 풀 때도 그 잘못된 길이 먼저 생각나는 거죠.
DP는 근육과 같습니다. 반복적인 연습만이 뇌에 새겨진 패턴을 바꿀 수 있어요. 이 글에서 소개한 커뮤니티의 시행착오를 여러분의 경험으로 삼고, 한 문제를 Top-Down → Bottom-Up → 공간 최적화까지 세 가지 방식으로 풀어보는 연습을 해보시길 강력히 추천합니다.
여러분의 첫 TLE를 응원합니다. 그게 진짜 DP의 시작이니까요.