백준 25759: 들판 건너가기

문제 요약

농부는 $N$개의 꽃이 일렬로 활짝 핀 들판을 왼쪽에서 오른쪽으로 걷고 있다. 심심한 농부는 들판에 핀 꽃을 몇 개 따서 꽃다발을 만들려 한다.

꽃다발의 아름다움은 꽃을 딴 순서대로 놓았을 때 (인접한 꽃의 아름다움 차이) $^2$의 전체 합으로 정의된다.

농부가 만들 수 있는 꽃다발의 가장 높은 아름다움 값을 구해주자.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

우선 $O(n^2)$의 다이나믹 프로그래밍을 생각했다. dp[i][j]는 마지막에 i번째 꽃을 고르고 그 다음에 j번째 꽃을 고르는 경우로 말이다. 그러나 당연히 시간초과가 발생한다.

이 문제에서 중요한 것은, 몇 번째 꽃을 골랐느냐가 아니라, 그 꽃의 아름다움 값이다. dp[i]는 지금까지 누적한, 꽃의 아름다움이 i값인 가장 높은 아름다움 값이다. 즉, 꽃을 0부터 n-1까지 탐색하며 dp 테이블 역시 함께 갱신된다.
마지막에는 dp[ary[n - 1]]을 출력함으로써, 가장 마지막에 갱신된 가장 높은 아름다움 값을 구하면 된다.
이 방법을 사용하면 시간복잡도는 $O(nm)$이 된다.

풀이 코드

import java.io.*;
import java.util.*;

public class Main {
	static int ary[], dp[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		ary = new int[n];
		dp = new int[101];
		for(int i = 0; i < n; i++)
			ary[i] = Integer.parseInt(st.nextToken());
		for(int i = 1; i <= 100; i++)
			dp[i] = -1;
		dp[ary[0]] = 0;
		for(int i = 1; i < n; i++) {
			for(int j = 1; j <= 100; j++) {
				if(dp[j] >= 0)
					dp[ary[i]] = Math.max(dp[ary[i]], dp[j] + (j - ary[i]) * (j - ary[i]));
			}
		}
		System.out.println(dp[ary[n - 1]]);
	}
}