[KOITP] 꽃 진열

출    처 : http://koitp.org/problem/IOI_1999_FLOWER/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	431	106 (25%)	78

문제

꽃집에서는 꽃을 꽃병에 꽂아 진열한다. F개의 서로 다른 꽃이 있고, V개의 꽃병들이 일렬로 있다. 꽃병들은 움직일 수 없고, 왼쪽에서부터 순서대로 1, 2, ..., V번까지 번호가 매겨져있다. 또한, 꽃은 1, 2, ..., F번까지 번호가 매겨져있다. 하나의 꽃병에는 하나의 꽃만 꽂을 수 있는데, 모든 꽃은 자신보다 큰 번호의 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다.

어떤 꽃을 어떤 꽃병에 꽂느냐에 따라 아름다움의 정도가 다르다. 이 아름다움의 정도는 점수로 수치화되어 표로 정리되어있는데, 만약 꽃이 꽂히지 않은 꽃병이 있는 경우, 해당 꽃병의 점수는 0점이다. 예를 들어, 아름다움의 점수는 아래와 같이 주어진다.

	꽃병
꽃		1	2	3	4	5
	1	7	23	-5	-24	16
	2	5	21	-4	10	23
	3	-21	5	-4	-20	20

꽃의 수, 꽃병의 수, 그리고 아름다움의 정도가 주어졌을 때, 모든 꽃을 꽃병에 꽂아 아름다움의 정도를 최대화시키자. 위와 같이 아름다움의 정도가 주어진 경우, 1번 꽃을 2번 꽃병, 2번 꽃을 4번 꽃병, 3번 꽃을 5번 꽃병에 꽂으면 23+10+20으로 최대 점수를 얻을 수 있다.

모든 꽃들은 어떤 꽃병에든 꽂혀야하고, 한 꽃병에는 최대 하나의 꽃만 꽂을 수 있다.

입력

첫 번째 줄에 꽃의 수 F와 꽃병의 수 V가 공백으로 분리되어 주어진다. (1 ≤ F ≤ V ≤ 100)

두 번째 줄부터 F개의 줄에 걸쳐 각 줄에 V개의 정수가 주어진다. 이는 아름다움의 정도를 나타내는 정수로, i번째 줄의 j번째 수는 i번 꽃이 j번 꽃병에 꽃혔을 때의 점수이다. (-50 ≤ 점수 ≤ 50)

출력

첫 번째 줄에 아름다움의 정도의 최대값을 출력한다.

힌트

모범코드 : http://ideone.com/o83nRS

입력 예제

3 5
7 23 -5 -24 6
5 21 -4 10 23
-21 5 -4 -20 20

출력 예제

53

< Comment >

 그다지 어려운 문제는 아니었는데, 문제를 정의할 때, 꽃병의 갯수와 꽃의 갯수를 착각해서 점화식을 세우고도 조금 헷갈려서 오래 걸렸습니다. 기본적으로 발상은 A번째 꽃병까지 B개의 꽃을 때의 최대 아름다움을 기준으로 DP 함수를 정의하고, 시작하였습니다. 기저 케이스는 꽃병의 수와 꽃의 수가 같을 경우 차례대로 넣는 경우입니다.

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

public class Flower {

	public static int F = 0;
	public static int V = 0;
	
	public static int matrix[][] = null;
	public static int dp[][] = null;
	
	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());
		
		matrix = new int[F+1][V+1];
		dp = 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++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 1 ; i <= F ; i++) {
			
			for (int j = i ; j <= V ; j++) {
				
				if (i == j) {
					
					int temp = 0;
					for (int k = 1 ; k <= i ; k++) {						
						temp += matrix[k][k];
					}
					
					dp[i][j] = temp;
				} else {					
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-1] + matrix[i][j]);
				}
				
			}
		}
		
		bw.write("" + dp[F][V]);
		bw.flush();
		bw.close();

	}
}