[백준 골드5 2240] 자두 나무, C++, DP

2240번: 자두나무

 

DP에 아직 익숙하지 않구나를 느낄 수 있었던 문제였다.

 

[C++] 백준(BOJ) 2240 - 자두나무

 

위 블로그에서 DP 힌트를 보지 않았다면 DFS, BFS로 풀려고 했을 것이다.

 

DFS나 BFS는 주로 그래프나 트리와 같은 구조에서 사용되는 탐색 알고리즘이지만, 이 문제는 단순한 그래프나 트리 구조가 아니다. 또한 자두의 위치는 시간에 따라 변하기 때문에 순차적으로 탐색하는 DFS나 BFS로는 이러한 시간적인 변화를 고려하기 어렵다.

그리고 T가 1000까지 늘어나기 때문에 완전탐색으로 한다면 2^1000까지 시간복잡도가 증가하기 때문에 완전탐색도 안된다.

 

그래서 DP를 선택하는 것이 맞는 선택이다

그러면 어떻게 DP를 적용할 수 있을까? 

DP[위치][남은 걸음수][시간] 이런 데이터 포맷으로 계산값을 저장하면 된다. 

 

 

위처럼 DP 시간, 위치, 남은 걸음 수 따른 자두 획득 개수를 기록해 놓으면 된다. 

 

개수를 계산하는 방식을 위치를 옮길 때와 그대로 있는 경우다.

 

(l = 위치, w = 남은 걸음수, i = 시간)

*그대로 있을 때 

 1.  획득한 경우 => DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i] + 1)

 2. 획득 못한 경우 => DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i])

 

* 위치를 옮길 때  (opp는 l의 반대)

 1.  획득한 경우 => DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i] + 1)

 2. 획득 못한 경우 => DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i])

 

따라서 위같은 원리로 코드를 작성하면 

// 2240 자두나무
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int DP[3][31][1001]; // 위치, 걸음수, 시간
vector<int> loc;
int T, W, V;

int solve(){
  DP[1][W][0] = 0;
  for (int i = 0; i < loc.size(); i++){
    for (int w = 0; w <= W; w++){
      for (int l = 1; l < 3; l++){ 
        if (DP[l][w][i] == -1)
          continue;
        
        // 그대로 가는 경우
        if (l == loc[i + 1]) // 다음 스텝에서 내 자리에 자두가 떨어지는 경우
          DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i] + 1); // 원래 있던 놈 vs 내가 지금 추가한놈
        else{
          DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i]);
        }

        // 옮기는 경우
        if (w - 1 >= 0){
          int opp = l == 1 ? 2 : 1;
          if (opp == loc[i + 1]) // 다음 스텝에서 내 자리에 자두가 떨어지는 경우
            DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i] + 1); // 원래 있던 놈 vs 내가 지금 추가한놈
          else
            DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i]);
        }
      }
    }
  }

  int MAX = -1;
  for (int w = 0; w <= W; w++){
    for (int l = 1; l < 3; l++){
      MAX = max(MAX, DP[l][w][T]);
    }
  }
  return MAX;
}

void print(){
  cout << "           ";
  for (int i = 0; i < loc.size(); i++){
    cout << loc[i] << "  ";
  }
  cout << endl; 
  for (int w = 0; w <= W; w++){
    for (int l = 1; l < 3; l++){
      cout << "l:" << l << ", w:" << w << ":";
      for (int i = 0; i < loc.size(); i++){
        cout << DP[l][w][i] << " ";
      }
      cout << endl;
    }
  }
}

int main(){
  cin >> T >> W;
  memset(DP, -1, sizeof(DP));
  loc.push_back(1);
  for(int i = 0; i < T; i++){
    cin >> V;
    loc.push_back(V);
  }

  cout << solve() << endl;
  return 0;
}

 

이와 같은 코드가 나온다.