[C++] 백준(BOJ) - 2240 : 자두나무 (DP)
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.
매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.
자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.
입력
첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.
출력
첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.
알고리즘
- DP
- 점화식
- 인접한 항들 사이의 관계식
- DP (Dynamic Programming)
- 중복되는 결과를 배열에 저장해서 같은 결과가 나오는 식은 배열에서 꺼내쓰는 방법
- 메모이제이션
- 어떤 상태 값을 자료구조(map, set, array)에 저장하는 것
- 이 상태 값을 정의하는 것이 DP의 핵심
- 점화식
어떠한 idx에서 모든 경우의 수 생각(완전탐색) + 메모이제이션
- DP의 조건
- 참조 투명성 : 입력을 제외한 외적 요소에 결과 값이 영향을 미치지 않아야 함
- Overlapping Subproblem : 겹치는 부분 문제가 존재해야 함
- Optimal Substructure : 최적 부분 구조를 가져야 함
- DAG(Directed Acyclic Graph) 구조를 가져야함
풀이
- 완전탐색으로 진행할 경우 $2^{30}$이상의 시간복잡도가 나옴
- 상태값이 총 3개이므로 3차원 배열이 필요 (idx(시간), tree(현 위치), W(cnt))
- DP의 4가지 기본 구조
- 기저사례 / 메모이제이션 / 로직 / 초기화
- 0, 1 두 가지 수의 경우 비트마스킹을 활용해서 bit flip 기법이나 wierd 연산자를 활용한다
- 초기화의 경우 결과값이 될 수 없는 것을 기준으로 설정한다
코드
// BOJ - 2240 : 자두나무
#include <bits/stdc++.h>
using namespace std;
int dp[1004][2][34], n, m, b[1004];
int go(int idx, int tree, int cnt)
{
// 1. 기저사례
if (cnt < 0) return -1e9;
//if (idx == n) return cnt == 0 ? 0 : -1e9; // 무조건 W번 움직였을 때의 코드
if (idx == n) return 0; // 최대 W만큼 움직였을 때
// 2. 메모이제이션
int& res = dp[idx][tree][cnt];
if (~res) return res;
// 3. 로직
return res = max(go(idx + 1, tree^1, cnt - 1), go(idx + 1, tree, cnt)) + (tree == b[idx] - 1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 4. 초기화
memset(dp, -1, sizeof(dp));
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> b[i];
cout << max(go(0, 1, m - 1), go(0, 0, m)) << '\n';
return 0;
}
평가
- DP의 4가지 기본구조를 기반으로 코드를 짜는 연습 필요
- 상태값을 파악하고 dp 자료구조를 어떻게 짤지 고민해야한다
