[KOITP] 꽃 진열 (문제ID : IOI_1999_FLOWER)

https://koitp.org/problem/IOI_1999_FLOWER/read/

Korea Olympiad in Informatics Training Program

 

이것도 전형적인 DP 문제..

(전형적인 DP라고 하면 부분문제 + 중복 메모이제이션)

 

조건을 살펴보자면,

문제에서 추출한 조건 1. 하나의 꽃병에는 하나의 꽃만 꽂을 수 있는데, 모든 꽃은 자신보다 큰 번호의 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다.  -> 모든 경우를 찾아봤을 때, 최악의 경우는 1번 2번 차례대로 골라나갔을 경우이다.      첫번째 꽃이 N개중 1번을 선택하면 두번째 꽃은 남은 N-1개중 2번을 선택..이런 순서대로 골라갈 경우 O(N!) 2. 첫 번째 줄에 꽃의 수 F와 꽃병의 수 V가 공백으로 분리되어 주어진다. (1 ≤ F ≤ V ≤ 100)   -> 최대 꽃이 100개일 경우 O(100!) 무작위로 절대 못품 3. i번째 줄의 j번째 수는 i번 꽃이 j번 꽃병에 꽃혔을 때의 점수이다. (-50 ≤ 점수 ≤ 50)  -> 점수가 0점이 나올수도, 음수가 나올수도 있다.

 

1번의 조건으로 인해 명확하게 부분문제를 볼 수 있다.

 

위 경우 첫번째 꽃이 꽃병에 꽂힐 경우는 1번, 2번, 3번, 4번, 5번이다. (일단 이 다음 꽃은 생각하지 않기로)

 

1번의 꽃병에 꽂을 경우를 생각해보면

아래 그림처럼 2번 꽃은 2번, 3번, 4번, 5번에 꽂을 수 있다. 

그 중 (부분 문제들 중) 최대의 아름다움을 가질 수 있는 점수를 선택할 것이다.

...

1번 꽃을 2번 꽃병에 꽂을 경우는 2번 꽃을 3번, 4번, 5번에 꽂을 경우인데

위에서 풀었으므로 그대로 캐시에서 가져다 쓰면 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class source {
	private static int F;
	private static int V;
	private static int[][] S; // 점수
	private static int[][] D; // 캐시

	private static int MIN = -9999;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		F = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		S = new int[F + 1][V + 1];
		D = new int[F + 1][V + 1];
		for (int i = 1; i <= F; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= V; j++) {
				S[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
        // 점수가 0이 될 경우가 있으므로 최소값으로 초기화
		for (int i = 0; i <= F; i++) {
			Arrays.fill(D[i], MIN);
		}

		bw.write(String.valueOf(dp(0, 0)));
		bw.flush();
		bw.close();
		br.close();
	}

	private static int dp(int f, int v) {
	    // 리프 값은 기냥 리턴
		if (f == F) return S[f][v];
		// 캐시에 초기화 값이 아닌 경우 이미 푼 문제이므로 리턴
		if (D[f][v] != MIN) return D[f][v];

		for (int i = v + 1; i <= V; i++) {
        	// 오른쪽 꽃병들 전부 탐색하면서 최대값 저장
			D[f][v] = Math.max(dp(f + 1, i) + S[f][v], D[f][v]);
		}

		return D[f][v];
	}
}