[백준] 17953: 디저트 - JAVA

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

 

풀이

M종류의 디저트를 N일동안 하루에 하나씩 먹어야 한다.

 

전날 먹었던 것과 같은 것을 먹으면 만족감이 반으로 주는데, N일동안 최대의 만족감을 구해야 한다.

 

2차원 dp 배열을 만들었다. 각 날짜에 각 디저트마다 전날의 dp배열의 값들을 토대로 갱신해줬다.

 

전날과 같은 맛이라면 2로 나눠 더해줬다.

 

---

 

메모리: 92884KB
시간: 552ms
언어: Java 11

import java.io.*;
import java.util.*;

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[][] dessert = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < n + 1; j++) {
                dessert[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                for (int k = 1; k < m + 1; k++) {
                    if (i != 1 && k == j) {
                        dp[i][j] = Math.max(dp[i - 1][k] + dessert[j][i] / 2, dp[i][j]);
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][k] + dessert[j][i], dp[i][j]);
                    }
                }
            }
        }

        int answer = 0;
        for (int i = 1; i < m + 1; i++) {
            answer = Math.max(dp[n][i], answer);
        }

        System.out.println(answer);
    }
}