[BOJ] #2240 자두나무

시간 제한	메모리 제한	정답 비율
2 초	128 MB	35.371%

 

2240번: 자두나무

 

문제

자두는 자두를 좋아한다. 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두가 허공에 있을 때 잡아야 하는데

매 초마다, **두 개의 나무 중 하나**의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다.

 

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

testcase 1

5 4
2
1
2
1
2

정답 4

 

 

 

 

메모리	시간
1532 KB	0 ms

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[3][1005][35], jado[1005];
int t, w, Max;
int main(){    
    scanf("%d%d", &t, &w);
    for (int i = 1; i <= t; i++) {
        scanf("%d", &jado[i]);
    }
    for (int i = 1; i <= t; i++) { // 시간
        for (int j = 0; j <= w; j++) { // 움직인 횟수
            if (jado[i] == 1) {
                dp[1][i][j] = max(dp[1][i - 1][j] + 1, dp[2][i - 1][j - 1] + 1);
                dp[2][i][j] = max(dp[2][i - 1][j], dp[1][i - 1][j - 1]);
            }
            else {
                if (i == 1 && j == 0) continue; // 1초 때 2번 자두나무에서 자두가 떨어지고 움직인 횟수가 없으면 못 먹는다.
                dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
                dp[2][i][j] = max(dp[2][i - 1][j] + 1, dp[1][i - 1][j - 1] + 1);
            }
        }
    }
    for (int j = 0; j <= w; j++) {
        Max = max(Max, max(dp[1][t][j], dp[2][t][j]));
    }
    printf("%d", Max);
    return 0;
}

 

• j - 1을 접근하는데도 j = 0 부터 시작해도 되는 이유. (질문 검색 - 질문 답변)
  
  j = 0 일 때 j-1이라는 인덱스에 접근하게 됩니다. 배열에서 -1 인덱스는 더 상위 차원에서 1을 뺀 최대 인덱스와 같으므로 여기에 0값이 들어있다면 정상작동할 것이고, 다른 값이 들어있다면 오답이 나오겠죠.