문제
https://www.acmicpc.net/problem/2579
풀이
얻을 수 있는 최대 점수를 찾는 문제이므로 브루트포스, 그리디, DP 순으로 문제에 접근해보았다.
브루트포스로 푼다면, 숫자 1과 2를 조합하여 계단의 총 개수 n을 만들 수 있는 모든 경우의 수를 구한 뒤 그 중에서 얻을 수 있는 최대 점수를 구할 것이다.
그런데, 1이 연속으로 3번 나오면 안 되기 때문에 이에 대한 처리를 따로 해줘야 하고, n은 최대 300이므로 이를 1과 2의 조합으로 나타낼 수 있는 모든 경우의 수를 다 구하면 시간이 너무 오래 걸린다.
그렇다면 그리디는..? 직관적으로 생각했을 때, 가능한 많은 계단을 밟을수록 얻는 점수는 커질 것이다. 단, 문제에 제시된 제약 조건 (연속된 세 개의 계단을 밟을 수 없다.) 때문에 모든 계단을 다 밟을 수는 없다. 그리디로 푸는 것도 어려운 거 같다.
DP로는 어떻게 풀어야 할까? 규칙성을 발견하여 일반화 된 점화식을 도출해보자.
DP가 적용되는 문제의 특징도 다시 리마인드 해보자!
- 최적 부분 구조 (Optimal substructure)
: 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
- 중복되는 부분 문제 (Overlapping subproblem)
: 동일한 작은 문제를 반복적으로 해결한다.
DP
참고: https://yabmoons.tistory.com/510
예를 들어, 7층짜리 계단이 있고 아래 층부터 차례대로 [1, 2, 3, 4, 5, 6, 7] 의 점수를 갖고 있다고 해보자.
시작점으로부터 한 계단 또는 두 계단씩 올라가며 점수를 계산할 건데, i번째 계단을 "반드시 밟았을 때" 얻을 수 있는 최대 점수를 구해보자.
결국 우리가 이 문제에서 구하고자 하는 답은 "n번째 계단을 밟았을 때 얻을 수 있는 최대 점수"인데, 문제에 "n번째 계단은 반드시 밟아야 한다"는 조건이 있다.
따라서 큰 문제를 쪼갠 작은 문제들의 해도 "i번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수"로 정의한다.
먼저, 첫번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수는? 당연히 1이다.
다음으로 두번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수는 1 + 2 = 3점이다.
- 시작점 - 2번 : 2점
- 시작점 - 1번 - 2번 : 3점
세번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수는? 연속된 3개의 계단을 모두 밟으면 안 된다는 조건이 있기 때문에 유의해야 한다.
- 시작점 - 1번 - 2번 - 3번 (X)
- 시작점 - 1번 - 3번 : 4점
- 시작점 - 2번 - 3번 : 5점
위의 결과에 따라, 3번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수는 5점이다.
그 다음으로, 네 번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수는?
- 시작점 - 1번 - 2번 - 4번 : 7점 --- (a)
- 시작점 - 2번 - 4번 : 6점 --- (b)
- 시작점 - 1번 - 3번 - 4번 : 8점
위의 결과를 보면, 항상 (a)가 (b)보다 클 수밖에 없다. 왜냐하면 (a)는 1번을 거치는데 , (b)는 그렇지 않기 때문이다.
따라서 아래와 같이 두 가지 케이스만 비교하면 된다.
- 시작점 - 1번 - 2번 - 4번 : 7점 --- (a)
- 시작점 - 1번 - 3번 - 4번 : 8점 --- (b)
이제 이 두 가지 경우의 수를 일반화 시킨 다음에, 그 식이 5번째 계단에도 적용되는지 확인해보자!
우선 (a)에서 시작점 - 1번 - 2번 부분은 "2번 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수"와 동일하다. 따라서 (a)를 다음과 같이 표현할 수 있다.
2번 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수 + 4번 계단을 밟았을 때 얻는 점수
반면에, (b)에서 시작점 - 1번 - 3번 부분은 "3번 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수"가 아니다!! 위에서 계산한 결과에 따르면, 시작점 - 2번 - 3번일 때 최대 점수가 나오기 때문이다.
그렇다면 (b)는 다음과 같이 표현할 수 있다.
1번 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수 + 3번 계단을 밟았을 때 얻는 점수 + 4번 계단을 밟았을 때 얻는 점수
이제 숫자 4를 N으로 바꿔서 일반화 시켜보자.
- (n-2)번 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수 + n번 계단을 밟았을 때 얻는 점수
- (n-3)번 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수 + (n-1)번 계단을 밟았을 때 얻는 점수 + n번 계단을 밟았을 때 얻는 점수
이러한 규칙이 5번 계단에도 적용되는지 확인해보자.
3번(n-2) 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수 + 5번(n) 계단을 밟았을 때 얻는 점수
→ 5 + 5 = 10 --- (a)
2번(n-3) 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수 + 4번(n-1) 계단을 밟았을 때 얻는 점수 + 5번(n) 계단을 밟았을 때 얻는 점수
→ 3 + 4 + 5 = 12 --- (b)
실제로 5번 계단을 반드시 밟았을 때 얻을 수 있는 점수를 모두 나열해보면 다음과 같다.
시작점 - 1번 - 2번- 4번 - 5번 : 12점 --- (b)- 시작점 - 1번 - 3번 - 5번 : 9점
시작점 - 2번 - 3번- 5번 : 10점 --- (a)- 시작점 - 2번 - 4번 - 5번 : 11점
5번 계단에 대해서는 위와 같이 4가지 경우가 나오지만, n이 커질수록 가짓수를 더 늘어날 것이다. 그런데 위에서 살펴봤듯이 부분 문제가 중복되어 있기 때문에, 결국 위에서 언급한 2가지 경우의 수로 줄일 수 있고 그 중에서 더 큰 값이 정답이 된다.
이를 코드로 구현하기 위해 dp 테이블을 다음과 같이 사용하자.
dp[a] = b → a번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수는 b이다.
그리고 dp[n]을 구하려면 다음 2가지 경우의 수를 비교하면 된다.
- dp[n - 2] + score[n]
- dp[n - 3] + score[n - 1] + score[n]
score는 각 계단의 점수를 저장하는 배열이다.
C++ 코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 301;
int dp[MAX];
int score[MAX];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> score[i];
}
dp[1] = score[1];
dp[2] = score[1] + score[2];
for(int i = 3; i <= n; i++){
dp[i] = max(dp[i - 2] + score[i],
dp[i - 3] + score[i - 1] + score[i]);
}
// n번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값
cout << dp[n];
return 0;
}
