문제 이해
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
<그림 1>
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
<그림 2>
계단 오르는 데는 다음과 같은 규칙이 있다.
계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
문제 접근
처음에 문제를 보고는 BFS나 DFS로 풀어도 괜찮겠다고 생각했다!
그래서 어떻게 계단의 점수를 저장할지에 대해서 생각하다보니 점수를 저장하는 방식이 일정한 규칙을 가지고 전에 DP로 풀었던 문제와 유사하다는 생각이 들어서 DP로 풀었다
DP의 가장 중요한 점은 점화식을 세우는 일이다.
따라서 점화식을 먼저 세워서 문제를 풀었다.
문제 풀이
점화식 세우기
DP 배열에는 점수의 합이 들어가게 된다.
DP에는 1칸전의 DP+이번 계단의 점수 or 2칸전의 DP + 이번 계단의 점수 둘 중 더 큰 값이 들어간다는 것을 간단하게 세울 수 있다!
하지만 문제에서 주어진 제한조건이 있다.
그것은 바로 3칸 연속해서 계단을 오를 수 없다는 것이다.
따라서 도착점을 기준으로 2칸전에 오른 경우는 그대로 두고, 1칸 전에 오른 경우에는 2칸전의 계단을 밟아서는 안된다. 따라서 dp[i-3] + stair[i-1] + stair[i]의 점화식이 탄생하게 된다
따라서 dp[i]를 나타내는 점화식은 아래와 같다.
dp[i] = max(dp[i-3] +stair[i-1]+ stair[i], dp[i-2] + stair[i])이 둘중 더 큰 값을 dp에 저장하게 된다.
결국 정답, 즉, 가장 마지막 계단에는 가장 큰 점수를 가진다.
DP풀이는 정말 코드가 한없기 간단해지는 모습을 볼 수 있다.
하지만 처음부터 감을 잘 못잡는다면 이만큼 어려운 문제가 없는 것 같다!
DP문제는 큰 문제를 작은 문제로 나누어 보는 것이 가장 중요하다.
위의 경우에서도 계단을 오르는 것을 1칸 전의 계단을 밟고 이번 칸을 밟았는지, 2칸 전의 계단을 밟고 이번 칸을 밟았는지 처럼 작은 문제로 분할해서 생각하다 보면 쉽게 점화식을 유도할 수 있을 것 이다.
제출 코드
import sys
N = int(sys.stdin.readline())
stair = [0]
for i in range(N):
stair.append(int(sys.stdin.readline()))
dp = [0 for i in range(N+1)]
dp[1] = stair[1]
for i in range(2, N+1):
dp[i] = max(dp[i-3] +stair[i-1]+ stair[i], dp[i-2] + stair[i])
print(dp[N])
