11058

백준 11058번

Link: 11058번: 크리보드

---

문제 설명

이번에도 DP 문제.

예전에 풀었어야 했는데 그땐 DP에 대해 너무 자신이 없어서 쫄아서 패스했던 기억이 난다.

이번에 DP를 제대로 공부하는 김에 풀어봤는데, 생각보다 금방 점화식을 찾아냈다.

물론 여러번 시도해보긴 했지만, 생각했던 점화식이 맞았다.

점화식에 대해 설명하자면 다음과 같다.

현재의 DP 인덱스가 i라고 가정하자.

우선 A만 누르는 경우는 직전 DP값에다 1을 더한 값이다.

이는 곧 DP[i] = DP[i-1] + 1과 같다.

이 다음부터가 꽤 복잡한데, 경우는 다음과 같다.

1) 현재 기준 3번 전 DP에서 Ctrl + A를 눌러 그때 입력된 A들을 모두 선택하고, 2번 전 DP에서 Ctrl + C를 눌러 선택된 것을 복사한 다음 1번 전 DP에서 Ctrl + V를 눌러 복사된 내용을 붙여넣는 경우

이는 곧 DP[i-3]에다가 DP[i-3]을 한번 더 쓰는 것과 같다.

따라서 DP[i] = 2 * DP[i-3] 이다.

2) 현재 기준 4번 전 DP에서 Ctrl + A를 눌러 그때 입력된 A들을 모두 선택하고, 3번 전 DP에서 Ctrl + C를 눌러 선택된 것을 복사한 다음 2번 전, 1번 전 DP에서 Ctrl + V를 눌러 복사된 내용을 붙여넣는 경우

이는 곧 DP[i-4]를 3번 쓰는 것과 같으므로, DP[i] = 3 * DP[i-4] 이다.

이 과정을 DP[0] * (i-1)까지 반복한다.

이 모든 경우의 수들의 최대값이 현재 DP값이 된다.

정답을 얻기 위해 예전 정답을 쌓아 나간다는 생각을 어거지로라도 하다 보니 점화식이 조금은 보이는 것 같다.

이런식으로 DP를 정복할 수 있을것 같다는 자신감을 좀 갖게 해준 문제였다.

---

정답 코드

//
// Created by Keith_Lee on 26/02/2019.
//

#include <iostream>
#include <vector>
#include <strings.h>

using namespace std;

int N;
long long DP[101];

long long max(vector<long long> v){
    long long result = -1;

    for(int i=0; i<v.size(); i++){
        if(v[i] > result){
            result = v[i];
        }
    }

    return result;
}

int main(){
    cin >> N;

    bzero(DP, sizeof(DP));

    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 3;
    DP[4] = 4;
    DP[5] = 5;
    DP[6] = 6;

    for(int i=7; i<=N; i++){
        vector<long long> temp;

        for(int j=3; j<=i; j++){
            temp.push_back(DP[i-j]*(j-1));
        }

        DP[i] = max(temp);
    }

    cout << DP[N] << '\n';

    return 0;
}

---