[백준] 9461 파도반 수열 - DP(동적계획법, Dynamic Programming) JAVA

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

9461번: 파도반 수열

코드설명

DP 문제입니다.

 

주어진 삼각형을 읽다보면, 규칙성이 보입니다.

 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ...

F(N) = F(N-2) + F(N-3) (N >= 3) 입니다.

혹은 문제에서 주어진 삼각형 그림을 보면, 삼각형의 크기가 N-2 삼각형, N-3 삼각형의 변의 합인것을 볼 수 있습니다.

 

DP로 각 위치를 갱신해가면서 메모리제이션합니다.

 

혹은 다른 규칙성도 보입니다.

F(N) = F(N-1) + F(N-5) (N >= 5)로 처리할 수 있습니다. 

 

또 중요점은 계산도중 int형(2^31) 의 범위를 벗어나는 경우가 있습니다. 

그러므로 long형으로 수정합니다.

코드

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

public class Main {
	public static int T, N;
	public static int[] arr = new int[100001];
	public static long[] dp = new long[101];
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	dp[0] = 1;
    	dp[1] = 1;
    	dp[2] = 1;
    	dp[3] = 2;
    	for(int i=3;i<=100;i++) {
    		dp[i] = dp[i-2] + dp[i-3];
    	}
    	
    	for(int t=0;t<T;t++) {
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		System.out.println(dp[N-1]);
    	}
    }
}

 

package Main;

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

public class Main {
    public static int N, T, M; 
    public static long answer = 0;
    public static long[] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		T = Integer.parseInt(st.nextToken());
		cache = new long[101];
		Arrays.fill(cache, -1);
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			answer = func(N - 1); 
			System.out.println(answer);
		}
		
	}
    
    public static long func(int n) {
    	if(n == 0 || n == 1 || n == 2) return 1;
    	if(n == 3 || n == 4) return 2;
    	if(n == 5) return 3;
    	if(cache[n] != -1) return cache[n];
    	
    	long ret = 0;
    	ret = func(n - 1) + func(n - 5);
    	return cache[n] = ret;
    }
    
}