BAEK_17953_디저트

25 Nov 2019 in Sidemenu / BaekJoon

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

17953. 디저트

날짜와 종류별 만족도가 주어졌을 때 마지막 날의 최대 만족도를 구하는 문제

• MAX(오늘 특정 dessert에 해당하는 만족도 + 전날의 종류별마다의 만족도)를 계산하며 채워나가면 된다.
• 단, 어제 먹은 종류일 경우 오늘의 만족도는 1/2가 되는것만 조심!!

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

public class Main {
	static int day, kind;
	static int[][] satisfaction;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		day = toInt(st.nextToken());
		kind = toInt(st.nextToken());
		satisfaction = new int[kind][day];
		for (int i = 0; i < kind; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < day; j++) {
				satisfaction[i][j] = toInt(st.nextToken());
			}
		}

		System.out.println(calcSatisfaction());

	}

	static int calcSatisfaction() {
		for (int i = 1; i < day; i++) {
			for (int j = 0; j < kind; j++) {
				satisfaction[j][i] = getMaxSatisfaction(i, j);
			}
		}
		return getFinalMaxSatisfaction();
	}

	static int getMaxSatisfaction(int day, int selected) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < kind; i++) {
			int mySatisfaction = i == selected ? satisfaction[selected][day] >> 1 : satisfaction[selected][day];
			max = max > mySatisfaction + satisfaction[i][day - 1] ? max : mySatisfaction + satisfaction[i][day - 1];
		}
		return max;
	}

	static int getFinalMaxSatisfaction() {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < kind; i++) {
			max = max > satisfaction[i][day - 1] ? max : satisfaction[i][day - 1];
		}
		return max;
	}

	static int toInt(String input) {
		return Integer.parseInt(input);
	}
}