https://www.acmicpc.net/problem/2579
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
<그림 1>
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
<그림 2>
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
예제 입력 1
6
10
20
15
25
10
20
예제 출력 1
75
문제 풀이
문제 접근을 경우의 수가 두 번 넘어서 계단을 밟는지 아니면 한 번만 넘어서 밟는지를 비교하여 둘 중 점수가 높은 쪽을 택하는 방식으로 접근하였다. 그러면 Math.Max()함수를 이용하여 두 수 를 비교한 후, 더 높은 점수를 가진 쪽으로 가는 것을 택하게 된다.
첫 번째 계단과 두 번째 계단은 경우의 수가 밟는다는 경우의 수 밖에 없으니 이 둘은 초기값으로 잡고간다. 그리고 3부터는 1번 3번을 밟는지 2번 3번을 밟는지의 변수가 생기기 시작하기 때문에 이 둘을 비교해준다.
4부터는 더 큰 변수가 생긴다.
dp[4] = 1, 2, 4 or 1, 3, 4
dp[5] = 1, 3, 5 or 2, 3, 5 or 1, 2, 4, 5
dp[6] = 1, 2, 4, 6 or 1, 3, 5, 6 or 1, 3, 4, 6
dp[7] = 1, 2, 4, 6, 7 or 1, 3, 4, 6, 7 or 1, 2, 4, 5, 7 or 1, 3, 5, 7 or 2, 3, 5, 7
앞서 말했던 두 번 넘어서 현재 수 n을 밟았는가 vs 한 번만에 밟았는가의 규칙성이다. 앞의 노란색 형광팬의 수는 그 이전 값 (dp[n - 2]) 에서 현재 수를 더한것이고, 한 번 만에 밟았는가는 dp[n - 3] 에서 현재의 수와 그 전의 수를 더한 것이다.
dp[6]이 곧 dp[7]의 빨간펜과 같지않냐고 할 수 있지만, 13567의 수가 더 높을 수 있기 때문에 즉, 연속해서 수를 밟는 문제가 생길 수 있고 높은 확률로 수가 커지기 때문에 이렇게 계산해줘야 연속된 수를 안밟는 규칙으로 간다.
그렇다면 식을 정리해보자면
dp[i] = Math.Max(dp[i - 2] + nums[i], dp[i - 3] + nums[i - 1] + nums[i]);
// dp[i - 2] + nums[i] (현재 수와 이전 수가 두 칸 차이날 경우)
// dp[i - 3] + nums[i - 1] + nums[i] (현재 수와 이전의 수가 한 칸 차이날 경우)
이렇게 된다.
정답
class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
int[] nums = new int[n + 1];
for(int i = 1; i <= n; i++)
{
nums[i] = int.Parse(Console.ReadLine());
}
int[] dp = new int[n + 1];
if(n == 1)
{
Console.WriteLine(nums[1]);
return;
}
if(n == 2)
{
Console.WriteLine(nums[1] + nums[2]);
return;
}
dp[1] = nums[1];
dp[2] = nums[1] + nums[2];
dp[3] = Math.Max(nums[1] + nums[3], nums[2] + nums[3]);
for (int i = 4; i <= n; i++)
{
dp[i] = Math.Max(dp[i - 2] + nums[i], dp[i - 3] + nums[i - 1] + nums[i]);
}
Console.WriteLine(dp[n]);
}
}
회고
문제를 역시 메모장이나 노트에 쓰면서 하다 보니 어느정도의 규칙성이 보인다. 문제에 답이 있다고해서 잘 읽고 약간의 노가다(?)를 하면 풀어지기는 하는데 그래도 여전히 어렵고 문제를 보면 무섭게 느껴지는게 DP문제 인 것 같다.