[백준] 2240번: 자두나무 - C++

문제 출처:https://www.acmicpc.net/problem/2240

---

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

저는 이 문제의 점화식을 구하지 못하여서 재귀를 이용하여 풀었습니다. 단 재귀 호출을 사용할경우 피보나치 재귀처럼 중복

호출이 매우 많아 100% 시간초과가 뜨기 때문에 자두의 각 상태에 대한 값을 저장 해 줄수 있는 DP 배열을 하나 만들어 중복

호출을 최대한 줄여 문제를 풀었습니다.

이 문제에서 한 가지 주의 할 점은 자두가 시작하자마자 옆으로 움직여 움직임 횟수를 1 줄이고 1번 나무 아래에서도 시작 할 

수 있다는 점입니다. 따라서 저는 메인 함수에 자두가 1번,2번 나무에서 시작하는 경우를 각각 호출 해 주었습니다. 

코드에 대한 설명은 주석으로 해 두었습니다.

전체 코드입니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cmath> #include <list> #include <queue> #include <stack> #include <map> #include <ctime> #include <string.h> using namespace std;   int dp[1001][31][3]; int *tree, maxPlum = -1, t, w;   void cal(int pos, int index, int moveCount, int plum) {          //현재 자두에 위치에 자두가 떨어진다면     if (tree[index] == pos)         plum++;          //자두나무에서 자두가 다 떨어지면 plum과 maxPlum을 비교     if (index == t - 1) {         maxPlum = maxPlum < plum ? plum : maxPlum;         return;     }          //DP배열에 자두 정보다 없다면 현재 정보를 저장     if (dp[index][moveCount][pos] == -1)         dp[index][moveCount][pos] = plum;     //DP배열에 이미 자두 정보가 있다면 현재 자두 개수와 비교하여 현재 자두가 더 많다면 교체     else if (dp[index][moveCount][pos] < plum)         dp[index][moveCount][pos] = plum;     //DP배열에 있는 자두가 현재 자두개수보다 많다면 그 이상은 볼 필요가 없으므로 함수 종료     else         return;          cal(pos, index+1, moveCount, plum);     //트리의 다음 높이에서 자두가 떨어지는 위치가 바뀐다면 자두의 움직임 -1 을 하고 재귀 호출     if (tree[index] != tree[index + 1] && moveCount > 0) {         pos = pos == 1 ? 2 : 1;         cal(pos, index+1, moveCount-1, plum);     } }   int main(void) {     scanf("%d %d", &t, &w);     tree = new int[t];     for (int i = 0; i < t; i++) {         scanf("%d", &tree[i]);     }     //dp배열      for (int i = 0; i < 1001; i++) {         for (int j = 0; j < 31; j++) {             for (int k = 0; k < 3; k++) {                 dp[i][j][k] = -1;             }         }     }     //자두가 1번 나무 밑에서 시작하는 경우     cal(1, 0, w, 0);     //자두가 2번 ㅏ무 밑에서 시작하는 경우     cal(2, 0, w - 1, 0);     printf("%d", maxPlum);     return 0; } Colored by Color Scripter

cs