문제
https://www.acmicpc.net/problem/2579
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
풀이
제한조건
- 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
접근방법
DP
문제가 작은 문제로 부터 큰 문제의 정답을 찾는 것이며
구하고자 하는 값이 최솟값/최댓값과 같은 형태의 문제이다.
위 두 단서로 부터 DP임을 알아낼 수 있다.
재귀를 이용한 하향식보다는, 반복문을 이용한 상향식으로 접근해보자.
문제에는 3가지 조건이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
각 조건이 어떤것을 의미하는지 이해해보자.
1. 점화식의 수립에 관한 힌트이다. i번째 값을 계산하기 위해 i-1번째 또는 i-2번째를 참고해야함을 알 수 있다.
2. 점화식에서 예외가 될 수 있는 항목.
3. 가장 마지막항을 구하는것을 알 수 있음.
자. 그럼 가장 단순하게 생각하면 아래와 같은 수식이 나온다
dp[k] : k번째 계단에서 나올 수 있는 최대 점수
dp[i] = max(dp[i-1]+arr[i], dp[i-2]+arr[i]단순하게 세운 수식에서 문제가 하나 있다.
바로 연속된 3개의 계단을 연속해서 밟은경우를 확인할 방법이 없다.
이는 조건2를 위배하는 항목이다.
조건2를 어떻게 처리할 수 있을까?
1. i번째 위치에서 j번 연속으로 밟았을때의 최대 점수 기록하기
2. 애초에 연속으로 밟지 않게 구성하기.
여기서는 2번 방법으로 진행했다.
연속으로 밟지 않게 코딩으로 구현해보자.
우선 dp[i-2]+arr[i]의 방식으로 구현할 경우, 중간에 한 칸이 비어있기 때문에 아무런 상관이 없다.
문제가 되는것은 이전칸의 최대에서 1칸 이동한 경우(dp[i-1]+arr[i]) 인데,
이를 어떻게 다르게 표현할 수 있을지 생각해보자.
이전칸(i-1)과 현재칸(i)을 밟기 위해서는 (i-2)칸을 밟지 않아야 한다.
즉, (dp[i-3] + arr[i-1] + arr[i])와 같은식으로 표현한다면,
이전칸과 현재칸을 포함하며, 최대의 점수를 얻는 방식을 나타낼 수 있다.
이제 코드로 나타내보자.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = stoi(in.readLine());
int[] arr = new int[N + 1];
for (int i = 1; i <= N; ++i)
arr[i] = stoi(in.readLine());
int[] dp = new int[N + 1];
if (N >= 1)
dp[1] = arr[1];
if (N >= 2)
dp[2] = arr[1] + arr[2];
for (int i = 3; i <= N; ++i) {
int oneStep = dp[i - 3] + arr[i - 1] + arr[i];
dp[i] = Math.max(dp[i], oneStep);
int twoStep = dp[i - 2] + arr[i];
dp[i] = Math.max(dp[i], twoStep);
}
System.out.println(dp[N]);
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}