[JAVA] 백준 11058번 : 크리보드

 

---

 

• 생각

먼저 1번부터 N번째 입력했을때 최댓값의 메모를위한 dp[N+1]부터 만들어 놓자.

 

N번째의 입력은 1번째버튼을 입력하거나 4번째 버튼을 입력해야한다.

1번째 입력을 했다 가정하고 dp[i]=dp[i-1]로 초기화를 한다.

4번째 버튼을 입력할땐 몇번 연속 4번째 버튼을 입력하였는지가 중요하다.

왜냐하면 4번째 버튼을 처음 입력하기 2개전의 값이 버퍼에 복사되고 

dp[i]=dp[k]*(4번째버튼 입력횟수+1)이 되기 때문이다.

 

• 코드

정답 코드 : 점화식을 찾아 구현하였다.

 

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

public class Main {
	static int N;
	static long[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		FindMaxValue();
		System.out.println(dp[N]);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		dp = new long[101];
	}

	public static void FindMaxValue() {
		for(int i = 1; i <= N; i++) {
			dp[i]=dp[i-1]+1;
			for(int j = 1; j <= i - 3; j++) {
				dp[i] = Math.max(dp[i], (j+1)*dp[i-(j+2)]);
			}
		}
	}

}