백준 2240

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

2240번: 자두나무

 

다른 분들이 만들어두신 DP 문제집 뒤지다가 문제 이름보고 귀여워서 풀었다.

아직도 3차원 배열을 DP에 활용하는 건 익숙하지 않음을 깨닫게 된 문제이다.... 써야 하는 것까진 인지를 했는데 조건 분기 나누는게 아직도 어렵다. A4한페이지 가득 채워가며 풀다가 ,,, 그냥 몇 번 움직였었는지를 배열의 마지막 인자로 넣으면 되었음을 ... 구글링을 통해 알아냈다. ㅋㅋㅋㅋㅋ 처음엔 그냥 이전에 움직였는가 / 안 움직였는가를 0,1로 표현했었는데 이러면 또 얼마나 움직였는지, 그 최대값이 안넘는지를 어떻게 알지에 대한 문제가 발생한다. 걍 내부에 클래스 하나 더 만들어서도 해봤는데 복잡해졌다. 걍 자두 최대개수만 int 로 기록해두고 메모리를 더 쓰더라도 처음부터 움직일 수 있는 최대 횟수까지 배열을 선언해두는 것이 깔끔하다

그나저나 이 말을 쓰면 스터디 사람들이 보다가 웃을수도 있겠지만 자두 먹고 싶다. 아무도 안 궁금하겠지만 내 최애 과일 중 하나.근데 글쓰면서 구분 기호로 자두 쓰려 했는데 자두 이모지가 ,,없네 그래서 그냥 또 다른 최애 과일 중 하나인 복숭아 쓰기로 함

 

 

🍑 3차원 배열 만들기

DP[time][tree][move] : time 초에 tree번 나무에 move 횟수만큼 움직인 상태일 때 가질 수 있는 자두의 최대 개수

아 참고로 tree 번호가 1,2이다 보니 input 받아서 0,1 로처리해도 되고 if문으로 쪼개도 된다. 

바보같이 처음에 1 -> 2 넘어가는걸 (1+1)%2 이런식으로 계산했더니 0 나와서 답이 나오지 않았었다 ^^...

 

🍑 move는 쭉 0일수도 있다. 그냥 1번 나무에서 쭉 떨어질 수도 있기 때문이다. 이러한 경우도 계산해줄 것 

🍑 또한 maxMove = 3이라면 아예 안움직이는 경우(0) ~ 3번 다 채워서 움직이는 경우까지 총 4개가 있다. 

int[][][] DP = new int[time+1][3][maxMove+1];

 

🍑 처음 시작 위치는 1번 나무이기 때문에, 첫 번째 자두 떨어지는 시점에 1번에서 떨어지느냐 2번에서 떨어지느냐 따라 초기화해줄 것 

int index = Integer.parseInt(br.readLine());
if (index == 1) {
	DP[1][1][0] = 1;
} else {
	DP[1][2][1] = 1;
}

🍑 메인 로직 

• 반복문에서 i는 시간을 나타낸다. 1초때를 미리 초기화해줬으므로 2초부터 time까지 반복
• 추가 설명
  • 1번 나무에서 자두가 떨어진다고 가정 (index == 1, index는 현재 자두 떨어지는 나무 번호)
    • DP[i][1][j] : 1번 나무에서 j번 움직인 상태로 가질 수 있는 자두 최대 개수  
      • i - 1초 전 1번에서 있었던 경우 - 움직이지 않고 그대로 받는다. 
        • DP[ i - 1 ][ 1 ][ j ] + 1
      • i - 1초 전 2번에서 있었던 경우 - 2번 나무에 j-1번 움직인 상태에서, 1번으로 옮긴다.  
        • DP [ i - 1 ][ 2 ][ j - 1 ] + 1
    • DP[i][2][j] : 2번 나무에 그대로 있다면, 1번에서 떨어지는 자두는 결국 못받는 것이다. 
      • (비효율적이긴 하지만) 이전에 1번 나무에 있었고, 2번 나무로 건너오는 경우 
        • DP [ i - 1 ][ 1 ][ j - 1 ]
      • 2번 나무에서 그대로 있는 경우
        • DP [ i - 1 ][ 2 ][ j ]
• 결국 최대 개수 구하는 것이기 때문에 Math.max로 처리 
• 위에서 언급한 한 번도 안 움직이는 경우 ( j  == 0 )은 else문에서 각각 처리. 움직임 횟수 (배열의 3번째 요소)는 0으로 고정해서 계산

for (int i = 2; i <= time; i++) {
    index = Integer.parseInt(br.readLine());
    for (int j = 0; j <= maxMove; j++) {
        if (j > 0) {
            if (index == 1) {
                DP[i][1][j] = Math.max(DP[i-1][1][j] + 1, DP[i-1][2][j-1]+1);
                DP[i][2][j] = Math.max(DP[i-1][2][j], DP[i-1][1][j-1]);
            }
            else {
                DP[i][2][j] = Math.max(DP[i-1][2][j]+1, DP[i-1][1][j-1]+1);
                DP[i][1][j] = Math.max(DP[i-1][1][j], DP[i-1][2][j-1]);
            }
        } else {
            if (index == 1) {
                DP[i][1][0] = DP[i-1][1][0] + 1;
                DP[i][2][0] = DP[i-1][2][0];
            }
            else {
                DP[i][1][0] = DP[i-1][1][0];
                DP[i][2][0] = DP[i-1][2][0] + 1;
            }
        }
    }
}

🍑 전체 코드 

import java.io.*;
public class p2240 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        int time = Integer.parseInt(split[0]);
        int maxMove = Integer.parseInt(split[1]);
        int answer = 0;

        int[][][] DP = new int[time+1][3][maxMove+1];
        int index = Integer.parseInt(br.readLine());
        if (index == 1) {
            DP[1][1][0] = 1;
        } else {
            DP[1][2][1] = 1;
        }


        for (int i = 2; i <= time; i++) {
            index = Integer.parseInt(br.readLine());
            for (int j = 0; j <= maxMove; j++) {
                if (j > 0) {
                    if (index == 1) {
                        DP[i][1][j] = Math.max(DP[i-1][1][j] + 1, DP[i-1][2][j-1]+1);
                        DP[i][2][j] = Math.max(DP[i-1][2][j], DP[i-1][1][j-1]);
                    }
                    else {
                        DP[i][2][j] = Math.max(DP[i-1][2][j]+1, DP[i-1][1][j-1]+1);
                        DP[i][1][j] = Math.max(DP[i-1][1][j], DP[i-1][2][j-1]);
                    }
                } else {
                    if (index == 1) {
                        DP[i][1][0] = DP[i-1][1][0] + 1;
                        DP[i][2][0] = DP[i-1][2][0];
                    }
                    else {
                        DP[i][1][0] = DP[i-1][1][0];
                        DP[i][2][0] = DP[i-1][2][0] + 1;
                    }
                }
            }
        }

        for (int i = 0; i <= maxMove; i++) {
            answer = Math.max(answer, Math.max(DP[time][1][i], DP[time][2][i]));
        }
        System.out.println(answer);
    }
}