[백준/17953] 디저트 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 골드5
출처 : 백준 - 디저트

🦧 문제 풀이 접근

DP를 통해 문제를 해결할 수 있다.
각각의 행당 이중for문으로 비교한다.

아래 코드에서
j와 k가 같을때는 현재 값, 이전 값+디저트값/2중 큰 값을 넣는다.
j와 k가 다를때는 현재 값, 이전 값+디저트값 중 큰 값을 넣는다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int desert[][] = new int[M][N];
        int DP[][] = new int[M][N];
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                desert[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i=0;i<M;i++)
            DP[i][0] = desert[i][0];
        for(int i=1;i<N;i++) {
            for(int j=0;j<M;j++) {
                for(int k=0;k<M;k++) {
                    if(j==k)
                        DP[k][i] = Math.max(DP[k][i-1]+desert[k][i]/2,DP[k][i]);
                    else
                        DP[k][i] = Math.max(DP[j][i-1]+desert[k][i],DP[k][i]);
                }
            }
        }
        int max=0;
        for(int i=0;i<M;i++)
            max = Math.max(max,DP[i][N-1]);
        System.out.println(max);
    }
}

🥇 결과

🎓 느낀점

어렵지 않은 DP 문제이지만 의외로 햇갈리는 문제였다.
내가 습관적으로 DP배열을 i를 새로, j를 가로로 인지를 해서 입력이 반대로 들어오니깐 코드를 짜는데 시간이 조금 걸렸다.