문제 해결 전략
-
문제를 읽어보면,, 완탐으로 한다고 하면 지금 상태를 3개 봐야한다.
=> 3개의 상태값 맞물려야함. -
1) 현재 시간,
-
2) 자두가 몇번 이동,
-
3) (문제에서 직접 언급은 없지만, ) 1번 나무, 2번 나무 선택
-> 일반적인 완탐으로 하기에는 전혀 부적절하다 생각함.
결론
=> 확실한 거는 상태값을 매겨서 자두를 얻을 수 있는 최대값을 구해야 한다. 생각했고, 3개의 상태값을 이용한 탑다운으로 진행하기로 결정함.
기저 사례
-
문제에서 t만큼의 나무 번호가 주어짐.
=> 비교 대상이다.
-
1) 코드에서 0으로 반환해야 함.
-> go 함수 내에서 비교 인덱스가 v[t] 와 비교하는 상황을 만들면 , out of range이기 때문이다.
if(ttime == t) return 0;- 2) 최대 w만큼을 움직이게 하고 싶다.
-> 그렇다면 w까지만 움직이게 해야 한다.
--> w를 초과하면 어떻게 처리할까????
: 일단 스킵.
일단 코드 작성.
- 일단 go 함수를 이렇게 작성할 수 있다.
: 기본적인 탑다운 코드 틀.
- 그리고 main으로 가서 생각을 해보자.
-> 문제에서는 1번 나무가 시작점이다.
핵십!
- 그런데 시작할때, 자두라는 놈이
자두 나무에 1번나무에 그대로 있거나, 2번 나무로 이동할수 있다.
// 반드시 1번에서 시작한다고는 안함.!
-> 그래서 이러한 코드를 작성함.
최대값 코드 작성하자.
- 가) 나무가 1번과 2번 나무 뿐이므로, 0번과 1번으로 인식해서 코드를 작성하면 이렇게 할 수 있따.
-> 다른 나무를 어떻게 표현할까? 생각해보면, 0과 1뿐이므로,
xor 연산을 사용함.
xor 연산
- 2개의 값이 다르면, 1 반환
- 2개의 값이 같으면, 0반환.
1 ^ 1 => 0 , 0 ^ 1 => 1
- 나) 현재 내가 있는 트리랑 v값을 비교해서 일치하면 +1올리고, 그렇지 않으면 0값을 2개의 함수에다가 더함.
중요! 기저사례
-
여기는 비교하는 여기서 out of Range 처리하기 위한 등호이고, 비교 대상이 완전히 끝났으므로 0 반환이다.
-
여기가 중요하다.
문제를 읽어보면, 입력값 w만큼만 이동을 해야 하는데, w를 초과하게 되면, 이를 0으로 반환해야 하는 것인가?
지문을 보면, 반드시 cnt만큼만 이동해야 한다고 했는데, 우리는 2개의 함수, 1)가만히 있기, 2)움직이기 코드가 있는 상황이고,
2)번 움직이는 코드에 대한 처리가 필요하다!
그래서 초과되는 cnt 움직였다고 하면 잘못된 상황이므로 가장 큰값을 반환하고 있는 것이다.
코드
#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <string>
using namespace std;
#include <string>
#include <vector>
int t, w;
vector<int> v;
int memo[1001][31][2];
// 3가지 상태를 맞물리면서 풀어야함.
int go(int ttime, int mov, int num)
{
if (mov > w)
return -1e9;
if (ttime == t)
return 0;
int& ret = memo[ttime][mov][num];
if (ret != -1)
return ret;
// 1일때 0으로
// 0일때 1로 변경해야 함.
int eat = (num == v[ttime] ? 1 : 0);
// 그대로
ret = eat + max(go(ttime + 1, mov, num),
go(ttime + 1, mov + 1, 1 - num));
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
// 변경되는 상태값이 2개뿐이고,
// 왼쪽 오른쪽으로 움직인다.
// 맨 처음에는 1에 있다.
// 매 순간 1 에 있을수도, 2에 있을 수도
// 를 진행하면서 최대로 자두나무를 받는 카운트는?
cin >> t >> w;
v.resize(t);
for (int i = 0; i < t; ++i)
{
cin >> v[i];
v[i] -= 1;
}
memset(memo, -1, sizeof(memo));
cout << max(go(0, 0, 0), go(0,1,1));
return 0;
}
🔥🔥🔥