[백준] 2240번 자두나무 C++ 코드

코드

#include <iostream>
#include <cstring>

using namespace std;

int t,w,a[1003], dp[3][32][1003]; // 상태 3개 필요

int go(int loc, int cnt, int idx) {
    if(cnt > w) return -987654321; // 움직이는 횟수가 넘은 경우
    if(idx == t) return 0;
    if(dp[loc][cnt][idx] != -1) return dp[loc][cnt][idx];
    
    // 3-loc을 하면 1또는 2가 나온다
    int move = (a[idx] == loc ? 0 : 1) + go(3 - loc, cnt + 1, idx + 1);
    int stop = (a[idx] == loc ? 1 : 0) + go(loc, cnt, idx + 1);
    dp[loc][cnt][idx] = max(move, stop);
    return dp[loc][cnt][idx];
}

int main() {
    cin >> t >> w;
    memset(dp, -1, sizeof(dp));

    for(int i = 0; i < t; i++) cin >> a[i];
    cout << go(1,0,0) << '\n'; // 1번 나무부터 시작, 0번 움직였고 0번 인덱스
    
    return 0;
}

풀이

2^30가지를 완전탐색으로 찾아볼 수는 없고, 이전 상태를 이용할 수 있을 거 같아서 dp를 이용했다. dp테이블은 위치, 움직인 횟수, 인덱스 3가지 상태가 필요해서 3차원으로 구성했다. 움직이지 않은 경우에 현재 위치와 값이 같은 경우 1을 더해주었다. 움직이는 경우에는 현재위치와 값이 같지 않은 경우에 1을 더해주었다. (움직였기 때문) 

 

위 코드에는 3-loc으로 깔끔하게 구현되어 있지만, 사실 처음에는 삼항연산자의 향연이었다. 1 또는 2의 상태를 고를 때 3 - x를 적용함으로써 다른 값을 얻을 수 있다고 한다. 또는 0,1로 바꿔서 ^를 이용해 토글하는 방법도 있다.