값 h와 숫자 목록 blacklist가 주어진 상황을 가정해 보겠습니다. 우리는 현재 높이 h에 서 있고, 작은 공 하나를 높이 0까지 굴려 내리는 게임을 진행하고 있습니다. 게임의 규칙은 다음과 같습니다.
- 짝수 번째 라운드(0부터 시작)에는 공을 1칸, 2칸, 또는 4칸 아래로 이동할 수 있습니다.
- 홀수 번째 라운드에는 공을 1칸, 3칸, 또는 4칸 아래로 이동할 수 있습니다.
- 일부 층(높이)은 블랙리스트에 등록되어 있으며, 공이 이 칸에 도달하면 즉시 사라집니다.
목표는 블랙리스트 칸을 피하면서 공이 높이 0에 도달하는 서로 다른 경로의 수를 구하는 것입니다. 답이 너무 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환합니다.
예제 이해하기
예를 들어 입력이 h = 5, blacklist = [2, 1]이라면 출력은 2가 됩니다.
- 첫 번째 방법: 라운드 0에서 한 칸 이동(5 → 4), 그다음 라운드에서 네 칸 이동(4 → 0)
- 두 번째 방법: 라운드 0에서 두 칸 이동(5 → 3), 그다음 라운드에서 세 칸 이동(3 → 0)
높이 1과 2는 블랙리스트에 포함되어 있으므로, 이 칸을 거치는 경로는 모두 제외됩니다.
풀이 접근 방식
이 문제는 동적 계획법(DP)으로 해결할 수 있습니다. 핵심 아이디어는 게임을 거꾸로 생각하여, 공이 높이 0에서 출발해 h까지 올라가는 경로를 세는 것입니다. 이동 순서를 뒤집어도 '짝수 라운드 → 홀수 라운드'의 교대 규칙은 그대로 유지되며, 원래 게임의 첫 이동은 반드시 짝수 라운드 규칙(1, 2, 4칸)을 따르므로 뒤집힌 경로의 마지막 이동 역시 짝수 규칙에 해당하게 됩니다.
단계별 풀이 과정은 다음과 같습니다.
- blacklist 목록을 집합(set)으로 변환하여 조회 속도를 높입니다.
- 시작점(h)이나 도착점(0)이 블랙리스트에 포함되어 있으면 가능한 경로가 없으므로 0을 반환합니다.
- 크기가 h+1인 dp 배열을 만들고 각 칸을 [0, 0]으로 초기화합니다. dp[i][0]은 마지막 이동이 짝수 라운드 규칙(1, 2, 4칸)에 해당하는 경로의 수, dp[i][1]은 홀수 라운드 규칙(1, 3, 4칸)에 해당하는 경로의 수를 의미합니다.
- 출발점을 나타내는 dp[0]은 [1, 1]로 설정합니다. 첫 이동의 유형을 어느 쪽이든 선택할 수 있기 때문입니다.
- 모듈러 값 m을 10^9 + 7로 설정합니다.
- i를 1부터 h까지 반복하면서 각 i에 대해 x ∈ {1, 2, 3, 4}를 시도합니다.
- i − x ≥ 0이고 i − x가 블랙리스트에 없는 경우에만 이동을 고려합니다.
- x ≠ 3일 때(x가 1, 2, 4 중 하나일 때) dp[i][0] += dp[i−x][1]
- x ≠ 2일 때(x가 1, 3, 4 중 하나일 때) dp[i][1] += dp[i−x][0]
- 매 반복마다 dp 값을 m으로 나눈 나머지로 갱신하여 값이 무한히 커지는 것을 방지합니다.
- 최종적으로 dp[h][0]을 반환합니다.
구현 코드
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(h, blacklist):
blacklist = set(blacklist)
if 0 in blacklist or h in blacklist:
return 0
dp = [[0, 0] for i in range(h + 1)]
dp[0] = [1, 1]
m = 10 ** 9 + 7
for i in range(1, h + 1):
for x in [1, 2, 3, 4]:
if i - x >= 0 and i - x not in blacklist:
if x != 3:
dp[i][0] += dp[i - x][1]
if x != 2:
dp[i][1] += dp[i - x][0]
dp[i][0] %= m
dp[i][1] %= m
return dp[h][0]
h = 5
blacklist = [2, 1]
print(solve(h, blacklist))입력
5, [2, 1]
출력
2
복잡도 분석
각 높이마다 최대 4개의 이동 옵션만 확인하므로 시간 복잡도는 O(h)이며, dp 배열 사용으로 인한 공간 복잡도 역시 O(h)입니다.