[틀림] 백준 2240 자두나무 c++ // 탑다운디피, 재귀디피 형식, 비트연산자, memset사용법

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

2240번: 자두나무

1. 탑다운디피

1. 디피는 기본적으로 "상태"를 "배열"에 저장하고

이미 저장된 경로는 더 연산안하고 배열에 저장된 값을 사용하는 것이다.

2. 이문제에서 "상태"는 {idx, 위치, 이동제한} 이다. 그 값은 그상태일때, 획득가능한 자두의 최대값이다.

 

2.비트연산자

1. 나무위치가 1,2로 주어졌지만 이를 0, 1로 바꾸면 코드가 매우 간결해지는 장점이 생긴다.

2. 장점 : if(0) , if(1)로 바로 활용가능

3. 장점 2 :  xor 연산자 ^ 로 위치상태를 매개변수에서 바로 바꿔버리기 가능

 

2.5 memset사용법

memset(배열이름, 0 or -1 , sizeof(배열이름))

// 배열이름만으로 모든차원의 모든 원소를 초기화 가능!

 

3. 재귀디피 형식

dfs(상태 정보):
	기저사례
    if(dp) return dp
    
    dp =  max (dfs(다음상태1), dfs(다음상태2) ) + 추가값
    return dp

 

4. 의사코드

1. 완탐 -> 2^30 -> 불가 - > dp?

2. 계산안했다는 의미로 -1으로 dp 초기화!

3. 이동 or 안이동 이분 dfs

4. 상태값을 배열에 저장

5. 해당 상태값을 이미 계산했다면(dp!= -1 )  , 재활용

 

5.전체코드

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int t, w, dp[1004][3][34]; //idx, 위치, 제한
vector<int> v;

//인덱스, 위치, !남은!이동횟수
int dfs(int idx, int where, int cnt) {
	//조건을 벗어난경로에는 -큰값배정 => 정답후보에서 배제하기 위함
	if (cnt < 0) {
		return -987654321;
	}
	// 노드뒤에서부터 시작값
	if (idx == t) return 0;

	//메모이제이션, 기존계산된값이 있다면 그거사용
	if (dp[idx][where][cnt]!=-1) return dp[idx][where][cnt];

	//이동 or 안이동
	//dfs(비트바꾸는경우 == 이동하는경우) , dfs(안이동) 중 큰값
	// + table값과 현재 위치가 같으면 +1
	// (뒤에 -1하는 이유는 1,2나무위치를 0,1로 바꾸기 위함!)
	dp[idx][where][cnt] = max(dfs(idx + 1, where ^ 1, cnt - 1), dfs(idx + 1, where, cnt))
		+ (where == v[idx] - 1); 

	return dp[idx][where][cnt];
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	memset(dp, -1, sizeof(dp)); //3차원배열 초기화시 유용 0, -1로만 초기화가능
	// -1이면 최초방문임!

	cin >> t>>w;
	for (int i = 0; i < t; ++i) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	

	// 0,1 로 나무위치 변경시 장점 : 비트연산자로 간단한 코드가능!
	// ex) n xor 1 -> 0,1 위치변경 / if(value)로 간단한 코드가능
	// 
	// level0 부터 바로 분기시작함.
	//후다닥움직여서 1로이동 or 그대로 0에 있는경우
	cout << max(dfs(0, 1, w - 1), dfs(0, 0, w));
	

	return 0;
}

 

* 2회독

• 리프노드 시작값은 return 0 임
• dp[] = max (...), reutrn dp 의 형태임
• 레벨0부터 시작 -> depth == t이면 리턴 / (depth > t) 아님
• dp는 아래 그림이 이해하기에 쉬움
  • 리프노드 (0)에서 시작해서 돌아오면서 둘중 큰값을 선택하는 것

#include<bits/stdc++.h>
using namespace std; 

int t,w;
int dp[1004][3][34]; // 초,위치,이동횟수, 값 : 그때 자두 갯수
int a[1004];

int dfs(int depth, int witch, int cnt) {
   if(cnt > w ) {
      return -987654321;
   }
   if(depth >= t) {
      return 0; //리프노드 시작값은 0
   }

   if(dp[depth][witch][cnt]!=-1) {
      return dp[depth][witch][cnt];
   }

   int & ret = dp[depth][witch][cnt];
   ret = max(dfs(depth+1, witch^1, cnt+1), dfs(depth+1, witch, cnt))
      +(witch == a[depth]);
   
   return ret;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   memset(dp,-1,sizeof(dp));
   cin>>t>>w;
   for(int i=0;i<t;++i) {
      cin>>a[i];
      a[i]--; // 0-idx로 바꾸기
   }

   cout<< max(dfs(0,0,0),dfs(0,1,1));
}