[백준] 2240: 자두나무

https://www.acmicpc.net/problem/2240

2240번: 자두나무

인간은 망각의 동물이라 그랬나..

요즘 바쁘다보니 알고리즘 풀이를 2주 정도 쉬었더니 엄청나게 실력이 대폭 줄어있었다..ㅠ

더 열심히 하자...ㅎㅎ

 

 

우선 점화식을 잘 세워야한다.

메모이제이션의 대상은 추후에도 계속 사용될 가치가 있는 값이어야 한다. 그리고 여기서는 단순히 최대의 자두를 고르는 것이 아니라 제한된 이동 수 안에서 자두의 수를 최대화해야한다.

그렇다면 점화식에 필요한 파라미터는 시간, 현재 위치, 이동 횟수이다.

 

그리고 다이나믹 프로그래밍에는 크게 2가지 방식의 구현 방법이 있다.

1. 낮은 단계부터 반복문으로 메모이제이션

2. 재귀함수로 depth를 스스로 만들어 메모이제이션

 

나는 연습 삼아 두 방식 모두 만들어보았다.

1. 낮은 단계부터 반복문으로 메모이제이션

이 문제에서 낮은 단계라 하면 한 번도 이동을 하지 않은 경우를 뜻한다.

 

이를 기반으로 점차 이동의 횟수를 늘려가며 이동횟수가 적은 값을 메모이제이션하면서 다이나믹 프로그래밍을 할 수 있다.

void move() {
    // 이동 횟수를 늘려나가며 메모이제이션
    for(int i = 1;i <= t;i++) {
        for(int j = 0;j <= w;j++) {
            int tree_num = trees[i];
            if(tree_num == 1){
                if(j == 0) {
                    score[i][0][1] = score[i - 1][0][1] + 1;
                    continue;
                }
                score[i][j][1] = max(score[i - 1][j][1] + 1, score[i - 1][j - 1][2] + 1);
                score[i][j][2] = max(score[i - 1][j][2], score[i - 1][j - 1][1]);
            }
            else {
                if(j == 0) {
                    score[i][0][1] = score[i - 1][0][1];
                    continue;
                }
                score[i][j][1] = max(score[i - 1][j][1], score[i - 1][j - 1][2]);
                score[i][j][2] = max(score[i - 1][j][2] + 1, score[i - 1][j - 1][1] + 1);
            }
        }
    }
}

2. 재귀함수로 depth를 스스로 만들어 메모이제이션

이 경우에는 직접 for문을 만드는 것이 아니라 함수를 호출해서 메모이제이션을 수행한다.

저번에 풀었던 세그먼트 트리의 호출 방식과 동일하다.

int move(int time, int move_cnt, int index) {
    if(score[time][move_cnt][index] != -1) {
        return score[time][move_cnt][index];
    }
    if(time == 0) return 0;
    
    int& answer = score[time][move_cnt][index];
    if(move_cnt == 0) {
        if(trees[time] == 1) {
            answer = move(time - 1, 0, 1) + 1;
        }
        else {
            answer = move(time - 1, 0, 2);
        }
    }
    else {
        if(trees[time] == index) {
            answer = max(move(time - 1, move_cnt, index) + 1, move(time - 1, move_cnt - 1, 3 - index) + 1);
        }
        else {
            answer = max(move(time - 1, move_cnt, index), move(time - 1, move_cnt - 1, 3 - index));
        }
    }
    
    return answer;
}

두 방식 모두 통과했고,

전체적인 코드는 아래와 같다.

/**
 https://www.acmicpc.net/problem/2240
 */
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int t, w;
int trees[1001];
// a초에 b번 움직여서 c(1,2)에 위치
int score[1001][31][3];
void move() {
    // 이동 횟수를 늘려나가며 메모이제이션
    for(int i = 1;i <= t;i++) {
        for(int j = 0;j <= w;j++) {
            int tree_num = trees[i];
            if(tree_num == 1){
                if(j == 0) {
                    score[i][0][1] = score[i - 1][0][1] + 1;
                    continue;
                }
                score[i][j][1] = max(score[i - 1][j][1] + 1, score[i - 1][j - 1][2] + 1);
                score[i][j][2] = max(score[i - 1][j][2], score[i - 1][j - 1][1]);
            }
            else {
                if(j == 0) {
                    score[i][0][1] = score[i - 1][0][1];
                    continue;
                }
                score[i][j][1] = max(score[i - 1][j][1], score[i - 1][j - 1][2]);
                score[i][j][2] = max(score[i - 1][j][2] + 1, score[i - 1][j - 1][1] + 1);
            }
        }
    }
}

int move(int time, int move_cnt, int index) {
    if(score[time][move_cnt][index] != -1) {
        return score[time][move_cnt][index];
    }
    if(time == 0) return 0;
    
    int& answer = score[time][move_cnt][index];
    if(move_cnt == 0) {
        if(trees[time] == 1) {
            answer = move(time - 1, 0, 1) + 1;
        }
        else {
            answer = move(time - 1, 0, 2);
        }
    }
    else {
        if(trees[time] == index) {
            answer = max(move(time - 1, move_cnt, index) + 1, move(time - 1, move_cnt - 1, 3 - index) + 1);
        }
        else {
            answer = max(move(time - 1, move_cnt, index), move(time - 1, move_cnt - 1, 3 - index));
        }
    }
    
    return answer;
}
int main() {
    cin >> t >> w;
    memset(score, -1, sizeof(score));
    trees[0] = 0;
    for(int i = 1;i <= t;i++) {
        cin >> trees[i];
    }
    for(int i = 0;i <= w;i++) {
        move(t, i, 1);
        move(t, i, 2);
    }
    
    int answer = 0;
    for(int i = 0;i <= w;i++) {
        answer = max(answer, score[t][i][1]);
        answer = max(answer, score[t][i][2]);
    }
    
    cout << answer <<'\n';
}