배열이나 문자열만 DP 문제가 되는 것은 아닙니다.
가끔은
특정 규칙으로 앞으로 이동할 때, 목표 지점까지 도달하는 방법 수를 묻는 문제도 자주 나옵니다.
이번 글에서는
한 번에 이동할 수 있는 칸 수가 정해져 있을 때,
목표 위치에 도달하는 서로 다른 방법의 수를 구하는 문제를 정리해보겠습니다.
이 문제는 DP의 기본 감각을 익히기 좋고,
조건을 조금만 바꾸면 더 일반적인 형태로도 확장할 수 있습니다.
문제
한 캐릭터가 일직선 맵에서 출발점 0에 서 있습니다.
이 캐릭터는 한 번 움직일 때
1칸 또는 2칸 앞으로 이동할 수 있습니다.
정수 N이 주어질 때,
캐릭터가 정확히 N칸 위치에 도달할 수 있는 서로 다른 이동 방법의 수를 구하는 함수를 작성해보겠습니다.
단, 이동 순서가 다르면 서로 다른 방법으로 봅니다.
실행 예시
N = 4일 때 가능한 방법은 5가지입니다.
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
따라서 정답은 5입니다.
처음 떠오르는 생각
현재 위치에 도달하는 마지막 움직임은 무엇이었을지 생각해보면 흐름이 단순해집니다.
어떤 칸 i에 도착하는 마지막 움직임은 두 가지뿐입니다.
i - 1에서 1칸 이동i - 2에서 2칸 이동
즉, i에 도착하는 방법 수는
바로 앞 칸까지 오는 방법 수와, 두 칸 앞까지 오는 방법 수를 더한 것과 같습니다.
핵심 아이디어
이 문제는 DP로 보면 아주 자연스럽습니다.
dp[i]를 i칸 위치에 도달하는 방법 수라고 하면, 점화식은 아래처럼 됩니다.
dp[i] = dp[i - 1] + dp[i - 2]
의미는 간단합니다.
- 마지막에 1칸 움직였다면
dp[i - 1] - 마지막에 2칸 움직였다면
dp[i - 2]
이 두 경우를 합치면 현재 칸에 도달하는 전체 경우의 수가 됩니다.
코드
기본형 풀이
def count_ways(n):
if n == 0:
return 1
if n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
공간 최적화 버전
이 문제는 직전 두 값만 필요하므로 배열 전체를 들고 있을 필요가 없습니다.
def count_ways(n):
if n == 0:
return 1
if n == 1:
return 1
prev2 = 1
prev1 = 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
코드 해설
왜 dp[0] = 1일까
이 부분은 처음 보면 조금 어색할 수 있습니다.
0칸에 도달하는 방법은
아무것도 하지 않는 경우 1가지로 봅니다.
이 기준이 있어야 이후 점화식이 자연스럽게 이어집니다.
왜 현재 위치가 이전 두 위치의 합일까
현재 칸에 오기 직전에는
반드시 1칸 전 또는 2칸 전에 있었어야 합니다.
즉 현재 칸의 방법 수는
그 두 위치까지 도달하는 방법 수의 합으로 만들 수 있습니다.
공간 최적화가 가능한 이유
dp[i]를 계산할 때 필요한 값은
dp[i - 1]dp[i - 2]
딱 두 개뿐입니다.
그래서 배열 전체를 저장하지 않고
직전 두 값만 들고 가도 결과를 구할 수 있습니다.
실행 예시
print(count_ways(0)) # 1
print(count_ways(1)) # 1
print(count_ways(2)) # 2
print(count_ways(3)) # 3
print(count_ways(4)) # 5
조건이 바뀌면?
이제 이동 규칙을 일반화해보겠습니다.
한 번에 1칸, 2칸만 갈 수 있는 게 아니라,
주어진 집합 moves 안에 있는 칸 수만큼 이동할 수 있다고 해보겠습니다.
예를 들어:
moves = [1, 3, 5]
라면 한 번에 1칸, 3칸, 5칸 이동할 수 있습니다.
이때도 목표 N칸에 도달하는 방법 수를 같은 방식으로 구할 수 있습니다.
일반화된 점화식
어떤 칸 i에 도착하려면
허용된 이동 크기 step마다 아래를 더하면 됩니다.
dp[i] += dp[i - step]
단, i - step >= 0일 때만 가능합니다.
즉 현재 위치에 올 수 있는 이전 위치들의 경우의 수를 모두 누적하면 됩니다.
일반화된 풀이
def count_ways_with_moves(n, moves):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for step in moves:
if i - step >= 0:
dp[i] += dp[i - step]
return dp[n]
일반화된 실행 예시
print(count_ways_with_moves(5, [1, 3, 5]))
이 경우에도 핵심은 같습니다.
현재 위치에 오기 직전 위치들의 경우의 수를 모두 더한다
이 구조만 유지하면 이동 규칙이 달라져도 같은 패턴으로 확장할 수 있습니다.
복잡도
기본형
- 시간 복잡도:
O(N) - 공간 복잡도:
O(N)
공간 최적화 버전은:
- 시간 복잡도:
O(N) - 공간 복잡도:
O(1)
일반화된 형태
허용된 이동 크기 집합 길이를 M이라고 하면:
- 시간 복잡도:
O(N * M) - 공간 복잡도:
O(N)
정리
이 문제의 핵심은 한 줄입니다.
현재 위치의 경우의 수 = 올 수 있는 이전 위치들의 경우의 수 합
처음에는 계단이나 이동 문제처럼 보여도,
실제로는 경우의 수를 세는 DP 기본 문제입니다.
기본형은 1칸 / 2칸 이동이고,
확장형은 주어진 이동 집합으로 일반화할 수 있습니다.
즉, 이 문제는
- 경우의 수 계산
- 점화식 세우기
- 공간 최적화
- 일반화된 DP
를 함께 연습하기 좋은 유형입니다.
※ 이 글의 문제 상황과 예시는 학습용으로 직접 재구성한 내용입니다.