[JAVA]2240 자두나무, 골드 5, dp

 📚 문제  

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

2240번: 자두나무

 

🔍 아이디어  

지정된 움직임 안에서 최대 몇 개의 사과를 먹을 수 있는가에 대한 문제이다.

0번 움직이면 1번칸,

1번 움직이면 2번칸,

2번 움직이면 1번칸,

즉 칸의 움직임에 따라 그 사람이 있는 위치가 정해진다.

 

따라서 이것을 이용하여 풀이하였다.

1-1) 먼저 0번 움직인 경우:  예외 처리를 적용해서 이전칸의 값을 받아오고

if (j == 0) score[i][j] = score[i - 1][j];

 

1-2) j 번 움직인 경우:  j번움직인 경우 i번째 사과를 받기 직전과, j-1번 움직인 경우 i번째 사과를 받은 경우의 max를 넣는다.

else score[i][j] = Math.max(score[i - 1][j], score[i][j - 1]);

 

2) 그리고 현재 있는 칸이 사과가 떨어진 위치라면 +1을 한다.

if (now == j % 2) score[i][j]++;

 

따라서 score[i][j]에는 i번째 사과가 떨어질때 최대로 사과를 받을 수 있는 경우이다.(꼭 j번 움직여야 하는것은 아니다, j-1번 움직인 경우에도 최댓값이 될 수 있다. 1번 과정에서 max를 갱신하면서 이동해서)

 

위 코드에서 1-2에서 들 수 있는 생각 만약 j-1움직인 상태에서 i번째 사과를 받았다면 2번에 의해서 중복으로 사과를 받을 수 있는거 아닌가 하는 의문이 들 수 있다.

움직인 칸이 한칸 차이 이므로 사과는 둘중에 한번만 받을 수 있다. max 갱신을 위해서 해당 값과 함께 비교하였다.

 

갱신하는 방법을 사용하지 않는 경우 아래와 같은 코드도 통과 가능하다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[][] score = new int[T + 1][W + 1];
        for (int i = 1; i <= T; i++) {
            int now = Integer.parseInt(br.readLine()) - 1;

            for (int j = 0; j <= W; j++) {
                if (j == 0) score[i][j] = score[i - 1][j];
                else score[i][j] = Math.max(score[i - 1][j], score[i - 1][j - 1]);

                if (now == j % 2) score[i][j]++;
            }
        }

        int max = 0;
        for (int temp : score[T]) {
            max = Math.max(temp, max);
        }
        System.out.println(max);
    }
}

 

7 2
2[0, 1, 1]
1[1, 1, 2]
1[2, 2, 3]
2[2, 3, 3]
2[2, 4, 4]
1[3, 4, 5]
1[4, 4, 6]

6

 

📝 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());//입력
        int W = Integer.parseInt(st.nextToken());//움직임

        int[][] score = new int[T + 1][W + 1];
        for (int i = 1; i <= T; i++) {
            int now = Integer.parseInt(br.readLine()) - 1;

            for (int j = 0; j <= W; j++) { //움직임
                if (j == 0) score[i][j] = score[i - 1][j];
                else score[i][j] = Math.max(score[i - 1][j], score[i][j - 1]);

                if (now == j % 2) score[i][j]++;
            }
        }
        System.out.println(score[T][W]);
    }
}

 

📝 중간과정을 확인하고 싶은 경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[][] score = new int[T + 1][W + 1];
        for (int i = 1; i <= T; i++) {
            int now = Integer.parseInt(br.readLine()) - 1;

            for (int j = 0; j <= W; j++) {
                if (j == 0) score[i][j] = score[i - 1][j];
                else score[i][j] = Math.max(score[i - 1][j], score[i][j - 1]);

                if (now == j % 2) score[i][j]++;
            }
            sb.append(Arrays.toString(score[i])).append("\n");
        }
        System.out.println(sb);
        System.out.println(score[T][W]);
    }
}