[백준] 1823 수확 - Java

 

 

 

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

13002번: Happy Cow

 

위의 문제와 동일한 문제이다.

 

 

항상 그렇듯 dp배열부터 정의해보자.

 

dp[i][j] = i ~ j 구간에서 수확했을 때 얻을 수 있는 최대 이익

 

이제 재귀를 사용한 top-down으로 풀지, 반복문을 사용한 bottom-up 방식으로 풀지 생각해야 한다.

여기서 판단의 기준이 되는 건 dp배열의 형태인데.. 지금은 재귀를 사용하는 편이 더 쉬워 보인다.

 

 

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

public class Main {			
	static int[][] dp;
	static int[] arr;
	static int N;	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));								

		N = Integer.parseInt(br.readLine());

		arr = new int[N+1];
		dp = new int[N+1][N+1];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for(int i=1; i<N+1; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}	
				
		System.out.println(solve(1, N, 1));

	}

	static int solve(int left, int right, int day){
		if(left > right){
			return 0;
		}		
		
		if(dp[left][right] != 0){
			return dp[left][right];
		}

		dp[left][right] = Math.max(arr[left] * day + solve(left + 1, right, day + 1), arr[right] * day + solve(left, right - 1, day + 1));
		
		return dp[left][right];
	}
}

 

 

 

재귀적 형태에 익숙해져야 한다.

연습 많이..