스코어가 있는 계단
각 계단 별로 점수가 있고 계단이 있고, 그 계단을 한칸, 두칸씩 올라갈 수 있고 연속해서 3개는 접할 수 없는 조건을 가진 문제들이다.
이 조건들을 정리하면
1. 1칸 혹은 2칸씩 이동 가능
2. 3개 연속으로는 불가능
이다.
가끔 포도주 마시기라던가 다른 형태로도 나온다. 아무튼 핵심은 DP 풀이라는점이다.
이 문제는 크게 두 가지 패턴으로 나뉜다.
마지막 계단을 밟아야 하는 패턴
마지막에 무조건 들려야 끝나는 패턴이다. 백준 2579번에 해당한다.
계단이 총 6개 있고, 10 20 15 25 10 20 이 각 계단별 값이라고 하자.
우선 첫번째 계단 dp[1]의 최대값을 생각해보면, 당연히 score[1]일 것이다. (10)
두번째 계단의 경우 score가 음수가 아닌이상 dp[1] + score[2]가 그 값이 될것이다. (30)
세번째 부터는 위에서 정리한 2번 규칙이 적용되어야한다.
1. 1번 계단 후 3번 계단
10 + 15 = 25
2. 2번 계단 후 3번 계단
20 + 15 = 35
따라서 35이다.
네번째 계단은 어떨까?
네번째도 마찬가지로 아래와 같이 될 것이다.
1. 2번 계단 후 4번계단
이 경우 절대로 3연계단이 안나오니깐, 2번까지의 최대값 dp[2] + score[4]가 된다.
2. 1번까지의 최대값 + 3번계단 후 4번계단
3번까지의 최대값을 넣으면 3연계단 오류가 생길수도 있으니 1번까지의 최대값 + 4번까지의 최대값으로 정해야한다.
그렇다면 마지막 계단(N)을 밟았다고 가정하면
1. n-1을 밟고 마지막을 밟은 경우
dp[n-3] + score[n-1] + score[n]이 된다.
2. dp[n-1]을 거치지 않고 온 경우
이 경우 무조건적으로 dp[n-2]를 밟고 왔다.
따라서 dp[n-2] + score[n]이 된다.
이를 점화식으로 정리하면 다음과 같다.
dp[i] = max((dp[i-3] + score[i-1] + score[i]), dp[i-2] + score[i]);
#include <iostream>
#include <algorithm>
#define MAX 300
using namespace std;
int score[301];
int dp[301];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> score[i];
}
dp[0] = 0;
dp[1] = score[1];
dp[2] = score[1] + score[2];
dp[3] = max(score[1], score[2]) + score[3];
for (int i = 4; i <= n; i++) {
dp[i] = max((dp[i-3] + score[i-1]), dp[i-2]) + score[i];
}
cout << dp[n];
}전체코드는 다음과 같다.
마지막을 안 거쳐도 되는 경우
백준 2156이다.
규칙과 유형은 동일하지만, 마지막에 꼭 안가도 되는 방식이다. 대신 이번문제는 계단이 아니라 포도주 마시기이다. (그만 마셔라 효주!)
포주주가 총 6개 있고, 6 10 13 9 8 1 이 각 포도주의 용량이라고 하자.
첫번째 포도주의 경우 당연히 score[1]이다.
두번째 포도주의 경우 경우가 두가지가 있다.
첫번째, 두번째를 연달아 마신 경우
첫번째만 마신 경우
두번째만 마신 경우
당연히 첫번째, 두번째를 연달아 마신 경우가 값이 클 수 밖에 없다. 따라서 dp[2] = score[1] + score[2]이다.
그렇다면 세번째 잔은 어떨까?
크게 나눠보면 세번째 잔을 마시는 경우와, 안마시는 경우 두가지로 나뉠것이다.
마시지 않는 경우
일단 이 경우는 3연 마시기 금지 조항에 걸릴 일이 없다. 따라서 이 경우 최대로 마실수 있는 양은 dp[n-1]이다.
이를 공식으로 정리하면 다음과 같다.
dp[n] = dp[n-1]
마시는 경우
이 경우는 조금 더 복잡하게 들어간다.
OXO
XOO
XXO
총 3가지의 경우가 있기 때문이다.
일단 3번째 경우는 무조건 될 수가 없기데 제거하고 생각하면,
n-2를 마시고 n을 마셨거나, n-1을 마시고 n을 마신 경우 두가지이다.
n-2를 마시고 n을 마신 경우, 3연 마시기 금지에 안걸린다. 따라서 dp[n-2]의 최대값을 쓰면 된다.
n-1의 경우 n까지 마시면 3연마시기에 걸릴 수도 있다. 따라서 [n-3]의 최대값 + score[n-1] + score[n]이 되어야한다.
이를 다시금 공식으로 정리하면 다음과 같다.
dp[i] = max(dp[i-3] + score[i-1] + score[i], dp[i-2] + score[i])
#include <iostream>
#include <algorithm>
#define MAX 300
using namespace std;
int score[10001];
int dp[10001];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> score[i];
}
dp[0] = 0;
dp[1] = score[1];
dp[2] = dp[1] + score[2];
for (int i = 3; i <= n; i++) {
dp[i] = max(score[i] + max(dp[i-3] + score[i-1], dp[i-2]), dp[i-1]);
}
int max = 0;
for (int i = 1; i <= n; i++) {
if (dp[i] > max) max = dp[i];
}
cout << max;
}전체코드는 위와 같다.
정리
위 두 유형은 dp하면 이거다! 싶을 정도로 자주 보이니깐 암기해두는게 좋을것같다.
