[2240]자두 나무 - c++

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

2240번: 자두나무

진짜 정말..... 너무 어려웠다 답을 봐도 왜 이렇게 풀었는지를 몰라 계속 봤고 지금은 조금 이해한 상태다

DP 진짜 너무 어렵다.... 에효....

---

아이디어

먼저 몇 가지 가능성을 보도록 하자

 

1. 현재 나의 위치에 자두가 떨어진다

   a. 가만히 있고 자두를 잡는다

 

2. 현재 나와 다른 위치에 자두가 떨어진다

   a. 다른 나무로 이동하여 자두를 잡는다

   b. 가만히 있으며, 떨어지는 것을 지켜본다

 

 

코드로 구현하기 전에 DP테이블 정의를 이렇게 했다.

//d[이동횟수][현재 나무위치][시간]
d[31][2][1001]

---

CODE

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int t, w;
int arr[1001];

int d[31][3][1001];

int main(){
  init();
  cin >> t >> w;
  for(int i =1; i <= t; ++i) cin >> arr[i];

  for(int j = 0; j <= w; ++j){
    for(int i = 1; i <= t; ++i){
      if(j == 0) d[j][0][i] = d[j][0][i-1] + (arr[i]==1);
      else{
        d[j][0][i] = max(d[j][0][i-1]+(arr[i] == 1), d[j-1][1][i-1]+(arr[i]==1));
        d[j][1][i] = max(d[j][1][i-1]+(arr[i] == 2), d[j-1][0][i-1]+(arr[i] == 2));
      }
    }
  }

  int ans = 0;
  for(int i = 0; i < 2; ++i)
    for(int j = 0; j <=w; ++j)
      ans = max(ans, d[j][i][t]);
  cout << ans;

  return 0;
}

 

하나하나 뜯어서 분석해 보자 솔직히 나도 쓰면서 다시 이해해 봐야겠다.

 

1. 입력

cin >> t >> w;
for(int i =1; i <= t; ++i) cin >> arr[i];

그 어떤 입력과 다를 것 없다

 

2. DP테이블 채우기

여기서부터가 진짜다..

// j = 이동 횟수
// i = 현재 시간
// d[이동횟수][현재 나무 위치][현재 시간]
// d[ j ][ 0 or 1 ][ i ]

for(int j = 0; j <= w; ++j){
    for(int i = 1; i <= t; ++i){
      if(j == 0) d[j][0][i] = d[j][0][i-1] + (arr[i]==1);
      else{
        d[j][0][i] = max(d[j][0][i-1]+(arr[i] == 1), d[j-1][1][i-1]+(arr[i]==1));
        d[j][1][i] = max(d[j][1][i-1]+(arr[i] == 2), d[j-1][0][i-1]+(arr[i] == 2));
      }
    }
  }

총 이동 횟수만큼 반복 + 총 시간 초만큼 반복

//1.
if(j == 0) d[j][0][i] = d[j][0][i-1] + (arr[i]==1);

한 번도 이동하지 않고 가만히 있는 경우를 위처럼 구현한 것

//2.
else{
	d[j][0][i] = max(d[j][0][i-1]+(arr[i] == 1), d[j-1][1][i-1]+(arr[i]==1));
	d[j][1][i] = max(d[j][1][i-1]+(arr[i] == 2), d[j-1][0][i-1]+(arr[i] == 2));
}

 

↓↓↓

//2.1
// j번 이동 해서 i초에 1번 나무로 온 경우
d[j][0][i] = max(d[j][0][i-1]+(arr[i] == 1), d[j-1][1][i-1]+(arr[i]==1));

// 1. d[j][0][i-1]+(arr[i] == 1)
// 1초 전에 이동하지 않은 경우
// 즉 1초 전에 움직이지 않은 경우 + 자두가 1번 나무에서 떨어진다면 +1

// 2.  d[j-1][1][i-1]+(arr[i]==1)
// 1초 전에 이동하여 1번 나무로 온경우
// 즉 이동하였기 때문에 2번 나무의 테이블에서 값을 가져온다 + 자두가 1번 나무에서 떨어진다면 +1

그리고 또 밑의 코드

// 2.2
// j번 이동하여 i초에 2번 나무에 온경우
d[j][1][i] = max(d[j][1][i-1]+(arr[i] == 2), d[j-1][0][i-1]+(arr[i] == 2));

// 1. d[j][1][i-1]+(arr[i] == 2)
// 1초전에 움직이지 않고 그대로 있던 경우 + 자두가 2번 나무에서 떨어진다면 +1

// 2. d[j-1][0][i-1]+(arr[i] == 2)
// 1초전에 1번 나무에서 2번나무로 옮겨온 경우 + 자두가 2번 나무에서 떨어진다면 +1

 

3. 결과

int ans = 0;
  for(int i = 0; i < 2; ++i)
    for(int j = 0; j <=w; ++j)
      ans = max(ans, d[j][i][t]);
  cout << ans;

---

이 문제에서 얻어 가야 할 것

1. 테이블의 각 차원에 의미를 담을 수 있다.

2. 사실 많이 풀어 보며 감을 잡는 게 얻는 것 아닐까?

문제를 풀며

답을 보면서 이해하는 것도 힘들었다... 답을 보고 있는데도 하기 싫었고 그만하고 싶었다.

그런데 이 문제를 넘지 않으면 난 그저 그런 상태로 남아 있을 거라고 생각하니, 갑자기 어떻게든 이해는 해야겠다는 오기가 생겼다.

그 결과 문제 풀이의 77% 이해한 것 같다.

문제에 대한 생각의 여러 가지 관점과 접근을 배운 것 같다.

계속 풀자 그냥 계속 풀자

 

---

2023-06-20

10일이 지나고 다시 한번 풀어 보았는데, 스스로 풀어 보려고 하니 여전히 어렵다.

다시한번 풀이를 보았고 이해하는 건 쉬웠다.

10일뒤에 다시 풀어 봐야지....