[KOITP] 막대기 자르기

출처 : http://www.koitp.org/problem/ROD_CUTTING/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	297	150 (51%)	132

문제

길이가 $N$인 막대기가 있다. 막대기를 길이가 자연수가 되도록 여러 조각으로 자를 수 있다. 각 길이에 대해 값어치가 있을 때, 값어치 합이 최대가 되도록 막대기를 자르자.

예를 들어, 길이가 4인 막대기가 있고 각 길이 별 값어치가 아래와 같다고 하자.

|  length  | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
|   cost   | 1 | 5 | 8 | 9 |

이 때, 길이 2인 막대기가 두 개가 되도록 전체 막대기를 자를 경우 전체 값어치가 10 되어 최대가 된다.

입력

첫 줄에 막대기의 길이 $N$이 주어진다. ($1\le N\le 3,000$)

둘째 줄에 $N$개의 자연수가 공백으로 구분되어 주어지는데, $i$번째로 주어지는 수는 길이가 $i$인 막대기의 값어치를 의미한다. 이 때 주어지는 수는 1,000를 넘지 않는다.

출력

첫 줄에 값어치 합이 최대가 되도록 막대기를 자를 때, 값어치 합을 출력한다.

힌트

예제 입력

4
1 5 8 9

예제 출력

10

< Comment >

 조금 조잡하게 짜여진 느낌이기는 하지만, 테스트 케이스가 그다지 크지 않았는지, 별 문제 없이 풀 수 있었습니다. 점화식을 정의할 때 조금 이리저리 실수를 했었습니다. 기본적으로 자르지 않은 경우와, 자른 경우를 구분해서 했어야 했는데, 일단 자르고나서, 두개의 합이 최대인 경우를 비교하다보니 전부 다 자르는 경우가 되어서 쉬운 문제임에도 불구하고 조금 헤매었습니다.

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

public class Stick {
    
    public static int N = 0;			// 막대의 길이		[ 1, 3000 ]
    public static int stick[] = null;		// 막대길이마다의 가치	( 0, 1000 ]
    public static int cache[] = null;	// 잘려진 길이에 따른 최대값 cache

    public static void main(String[] args) throws Exception {
	
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	N = Integer.parseInt(br.readLine());
	stick = new int[N+1];
	cache = new int[N+1];
	
	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int i = 1 ; i <= N ; i++) {
	    stick[i] = Integer.parseInt(st.nextToken());
	}
	
	int answer = dp(N);
	
	bw.write(String.valueOf(answer));
	bw.flush();
	bw.close();
    }
    
    // 길이가 주어졌을 때, 가치가 최대로 되도록 자른 값을 리턴
    public static int dp (int n) {
	
	if (n == 1) {
	    return cache[1] = stick[1];
	} else if (cache[n] != 0) {
	    return cache[n];
	}
	
	int temp = 0;
	int ret = 0;
	for (int i = 1 ; i < n ; i++) {
	    temp = Math.max(stick[n], dp(i) + dp(n-i));
	    ret = Math.max(ret, temp);
	}
	
	return cache[n] = ret;
    }
}

아래쪽은 함수를 미호출 하고 Buttom-Up 식으로 구현한 소스입니다.

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

public class RodCut {
	
	public static int N = 0;
	public static int costByLength[] = 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));
		
		N = Integer.parseInt(br.readLine());
		
		costByLength = new int[N+1];
		dp = new int[N+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1 ; i <= N ; i++) {
			costByLength[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[1] = costByLength[1];
		for (int i = 2 ; i <= N ; i++) {
			
			for (int j = 1 ; j <= i ; j++) {
				dp[i] = Math.max(costByLength[j] + dp[i-j], dp[i]);
			}
		}
		
		bw.write("" + dp[N]);
		bw.flush();
		bw.close();
	}
}