본문 바로가기
Algorithm Theory/Dynamic Programming

[DP] [BOJ 2579] 계단 오르기

by hyeyoo 2020. 3. 30.
※ 이 블로그의 글은 글쓴이가 공부하면서 정리하여 쓴 글입니다.
※ 최대한 내용을 검토하면서 글을 쓰지만 틀린 내용이 있을 수 있습니다.
※ 만약 틀린 부분이 있다면 댓글로 알려주세요.

 

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩

www.acmicpc.net

문제

 

계단을 한 번에 최대 2칸까지 올라갈 수 있을 때, (연속된 세 칸을 밟을 수 없다.) n번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 구하는 문제

 

해석

이 문제에서 "N 번째 계단에서 얻을 수 있는 최대 점수"는 규칙에 따라서 두 가지로 나누어볼 수 있다.

 

1. N-1번째 계단에서 N번째 계단으로 넘어온 경우

2. N-2번째 계단에서 N번째 계단으로 넘어온 경우

(N번째 계단에 오르는 문제를 더 작은 문제로 분할하고, 이로부터 더 큰 문제를 해결할 수 있기 때문에

DP로 해결할 수 있다.)따라서 처음에 이 문제를 보면 식을 이렇게 세우게 된다.

 

d :  N에 따른 정답을 저장하는 배열

score: N번째 정답에서 얻을 수 있는 점수

d[N] = MAX(d[N-1], d[N-2]) + score[N]

 

하지만 이 문제에 있는 "연속된 세 계단을 밟으면 안된다"는 조건이 이 문제를 어렵게하는데, [N-1] -> [N]으로 넘어오는 경우 중에서, 그림에서 처럼 [N-2] -> [N-1] -> [N]를 제외해야한다. [N-1] -> [N]으로 넘어오는 경우는 두 가지 방법 ([N-3] -> [N-1] -> [N], [N-2] -> [N-1] -> [N])이 있으므로, 나머지 하나인 [N-3] -> [N-1] -> [N] 이렇게 넘어오는 경우만 세어주면 된다. (이해가 잘 되지 않는다면 그림을 다시 보자.)

 

따라서 식은 다음과 같이 세워야 한다.

d[N] = MAX(d[N-2], d[N-3] + score[N-1]) + score[N])

 

구현

 

댓글