백준 문제 주소 https://www.acmicpc.net/problem/2579
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
<그림 1>
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
<그림 2>
계단 오르는 데는 다음과 같은 규칙이 있다.
계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
6
10
20
15
25
10
20
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
75
출력해야하는 값이 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값이므로 배열에서 계속 더하면서 구하면 될 것 같다.
그리고 마지막 도착 계단은 반드시 밟아야하기 때문에 이를 고려해서 규칙을 만들어야한다.
규칙에 맞게 마지막 계단을 밟는다고 가정하면, 마지막 계단의 두 칸 전의 계단을 밟고 마지막 계단을 밟을 수 있다.
또한 마지막 계단의 한 칸 전의 계단을 밟고 마지막 계단을 밟을 수 있다. 두 과정 중에 값이 더 큰 것을 고르면 된다.
END 부분을 계산한다고 하면 dp[END] = arr[END] + max(dp[END-2], dp[END-3] + arr[END-1]로 나타낼 수 있다. 따라서 이 공식을 전체 부분에 적용해서 계산하면 된다. 하지만 i - 3을 고려하면, 0부터 2까지의 dp 배열 값은 수동으로 넣어줘야한다.
Python 풀이(실패)
import sys
input = sys.stdin.readline
arr = []
dp = []
n = int(input())
for _ in range(n):
arr.append(int(input()))
dp.append(arr[0])
dp.append(arr[0] + arr[1])
dp.append(arr[2] + max(dp[0], arr[1]))
for i in range(3,n):
dp.append(arr[i] + max(dp[i-2], dp[i-3] + arr[i-1]))
print(dp.pop())런타임에러(InDexError)가 나왔다. n이 1부터 3사이일 때를 고려하지 않았기 때문이다..
예전부터 큰 수인 경우만 생각하고 작은 수의 경우를 고려하지 못하는 경우가 종종 있었다. 반성하고 다음부터는 좀 더 꼼꼼하게 생각해야겠다!
Python 풀이(성공)
import sys
input = sys.stdin.readline
arr = []
dp = []
n = int(input())
for _ in range(n):
arr.append(int(input()))
if n == 1:
print(arr[0])
elif n == 2:
print(arr[0]+arr[1])
else :
dp.append(arr[0])
dp.append(arr[0] + arr[1])
dp.append(arr[2] + max(dp[0], arr[1]))
for i in range(3,n):
dp.append(arr[i] + max(dp[i-2], dp[i-3] + arr[i-1]))
print(dp.pop())
Kotlin 풀이
import java.io.*
import java.util.*
fun main(args: Array<String>)
{
val br = BufferedReader(InputStreamReader(System.`in`))
val n = br.readLine().toInt()
val arr = Array(n){0}
val dp = Array(n){0}
for (i in 0 until n) {
val st = StringTokenizer(br.readLine())
arr[i] = st.nextToken().toInt()
}
when(n) {
1 -> println(arr[0])
2 -> println(arr[0]+arr[1])
else -> {
dp[0] = arr[0]
dp[1] = arr[1] + dp[0]
dp[2] = arr[2] + Math.max(dp[0], arr[1])
for (i in 3 until n) {
dp[i] = arr[i] + Math.max(dp[i-2], dp[i-3] + arr[i-1])
}
println(dp[n-1])
}
}
}
