17953-디저트

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

17953번: 디저트

전형적인 DP 문제이다.

위 그림과 같이 디저트의 개수가 10개 이하이므로 이전의 디저트 행복도의 값과 다음 행복도의 합을 비교하여 더 큰 값을 앞에다 넣어주는 방식을로 구현하였다. 같은 디저트를 섭취할 경우에는 다음 디저트의 행복도를 2로 나눈 값으로 비교하였다.

package DP;

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

public class N17953F {
    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());
        ArrayList<ArrayList<Integer>> happy = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            happy.add(new ArrayList<>());
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                happy.get(i).add(Integer.valueOf(st2.nextToken()));
            }
        }
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j <m ; j++) {
                int cur = happy.get(j).get(i+1);
                for (int k = 0; k < m; k++) {
                    if(k == j){
                        happy.get(j).set(i+1,Math.max(happy.get(j).get(i+1),happy.get(k).get(i)+cur/2));
                        continue;
                    }
                    happy.get(j).set(i+1,Math.max(happy.get(j).get(i+1),happy.get(k).get(i)+cur));
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; i++) {
            max = Math.max(max, happy.get(i).get(n-1));
        }
        System.out.println(max);
        
    }
}

DP문제는 생각을 어떤 방식으로 하는지에 따라 난이도가 갈리는 듯 하다.