문제 설명
n개의 계단과 숫자 k가 주어졌다고 가정해 보겠습니다. 우리는 처음에 0번째 계단에 서 있으며, 한 번에 1칸, 2칸 또는 3칸씩 올라갈 수 있습니다. 다만 3칸씩 오르는 동작은 최대 k번까지만 허용됩니다. 이 조건 안에서 계단 꼭대기(n번째 계단)까지 도달할 수 있는 방법이 총 몇 가지인지 구하는 것이 목표입니다.
예제
입력이 n = 5, k = 2라면 출력은 13입니다. 계단을 오를 수 있는 서로 다른 방법은 아래와 같습니다.
- [1, 1, 1, 1, 1]
- [2, 1, 1, 1]
- [1, 2, 1, 1]
- [1, 1, 2, 1]
- [1, 1, 1, 2]
- [1, 2, 2]
- [2, 1, 2]
- [2, 2, 1]
- [1, 1, 3]
- [1, 3, 1]
- [3, 1, 1]
- [2, 3]
- [3, 2]
풀이 접근 방식
이 문제는 메모이제이션을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "지금까지 3칸 오르기를 몇 번 사용했는지"를 함께 추적하는 것입니다. 알고리즘의 단계는 다음과 같습니다.
- 기저 사례 처리: n이 0이면 1을 반환하고, n이 1이면 역시 1을 반환합니다.
- k 값 조정: k := min(k, n)으로 설정합니다. 계단이 n개뿐이므로 3칸 오르기를 n번보다 많이 사용할 수 없기 때문입니다.
- 메모 테이블 생성: (n+1) × (k+1) 크기의 2차원 배열 memo를 만듭니다. 여기서 memo[j][i]는 "3칸 오르기를 최대 j번 사용할 때 i개의 계단을 오르는 방법의 수"를 의미합니다.
- 초기값 설정: r이 0부터 k까지 각 행에 대해 memo[r][0] = 1, memo[r][1] = 1, memo[r][2] = 2로 초기화합니다.
- k = 0인 경우 처리: i가 3부터 n까지 memo[0][i] = memo[0][i-1] + memo[0][i-2]로 계산합니다. 3칸 오르기를 전혀 사용할 수 없으므로 1칸과 2칸 오르기만 고려합니다.
- DP 점화식 적용: j를 1부터 k까지, i를 3부터 n까지 반복하면서 다음을 수행합니다.
- count := i // 3 — i칸을 오르려면 최소 count번의 3칸 오르기가 필요합니다.
- count ≤ j라면 3칸 오르기를 충분히 사용할 수 있으므로 memo[j][i] = memo[j][i-1] + memo[j][i-2] + memo[j][i-3]
- 그렇지 않다면 3칸 오르기 사용 횟수가 부족한 상황이므로, 하나 적게 사용한 상태에서 가져와야 합니다. 즉 memo[j][i] = memo[j][i-1] + memo[j][i-2] + memo[j-1][i-3]
- 결과 반환: 최종적으로 memo[k][n]을 반환합니다.
구현 코드
아래는 위 알고리즘을 파이썬으로 구현한 예제입니다.
예제 코드
class Solution:
def solve(self, n, k):
if n==0:
return 1
if n==1:
return 1
k= min(k,n)
memo=[[0]*(n+1) for _ in range(k+1)]
for r in range(k+1):
memo[r][0]=1
memo[r][1]=1
memo[r][2]=2
for i in range(3,n+1):
memo[0][i]=memo[0][i-1]+memo[0][i-2]
for j in range(1,k+1):
for i in range(3,n+1):
count = i//3
if count<=j:
memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j][i-3]
else:
memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j-1][i-3]
return memo[k][n]
ob = Solution()
print(ob.solve(n = 5, k = 2))
입력
5, 2
출력
13
이처럼 2차원 DP 테이블에 "계단의 개수"와 "3칸 오르기 사용 횟수" 두 가지 상태를 함께 기록하면, 3칸 오르기 횟수 제한이 있는 계단 오르기 문제도 정확하게 해결할 수 있습니다.