[백준] 2240번 자두나무 c++

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

2240번: 자두나무

 

문제

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

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

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

입력

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

출력

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

 

 

접근방식

- 재귀방식으로 접근했다.

- 재귀만으로는 시간초과가 발생하므로 dp를 활용한다.

- dp[현재시각][움직일수있는횟수][현재위치]로 설정했다.

 

- 탐색을 진행하면서 가지치기를 하는 경우

1. 이미 들어 있는 dp 값이 현재 sum 값보다 큰 경우 -> 같은 조건에서의 값이 더 작은 것이므로 굳이 탐색을 이어갈 필요가 없다.

2. 현재시각부터 남은 시간 동안 모든 자두를 먹는다고 가정해도 maxnum보다 작은 경우

 

#include <iostream>
#include <algorithm>

using namespace std;

int t;
int input[1000][3]={0};
int dp[1000][30][2]={0};
int maxnum=0;
void jadoo(int move, int x, int depth, int sum){
  if(depth > t) return ;
  if(input[depth][x]==1)
    sum++;

  if(dp[depth][move][x]==0){
    dp[depth][move][x] = sum;
  }else if(dp[depth][move][x] < sum){
    dp[depth][move][x] = sum;
  }else{ // dp값이 이미 더 크다면 탐색할 필요가 없다. 같은 조건에서 값이 더 작은 것이기 때문이다.
    return ;
  }

  if(maxnum < sum) maxnum = sum;

  // 남은 시간동안 자두를 모두 먹는다고 해도 maxnum보다 작다면, 굳이 탐색할 필요가 없다.
  if(t-depth-1 + sum < maxnum) return ;
  
  if(move!=0 && x==1){
    jadoo(move-1, x+1, depth+1, sum);
    jadoo(move, x, depth+1, sum);
  }else if(move!=0 && x==2){
    jadoo(move-1, x-1, depth+1, sum);
    jadoo(move, x, depth+1, sum);
  }else
    jadoo(move, x, depth+1, sum);
}
int main(){
  int w;
  cin >> t >> w;
  for(int i=0; i<t; i++){
    int x;
    cin >> x;
    if(x==1) input[i][1]=1;
    if(x==2) input[i][2]=1;
  }
  // 옮기고 시작하는 경우도 함께 고려해 준다.
  jadoo(w, 1, 0, 0);
  jadoo(w-1, 2, 0, 0);
  printf("%d\n", maxnum);
}

 

느낀점

예전에 그리디 문제풀면서 배웠던 개념(남은 시간동안 자두를 모두 먹는 경우와 현재 max값을 비교)을 적용해서 시간을 단축할 수 있어서 뿌듯했다.

거의 2배로 시간을 단축했다!

그리디한 개념을 추가하여 효율성을 높인 결과