[백준 - 9461번] 파도반 수열 - JAVA 정리 및 해설

오늘은 파도반 수열에 대해서 정리해보도록 하겠습니다. 

파도반 수열은 두방식으로 둘다 풀리는 문제중 하나입니다. Top-down방식과 Bottom-Up 방식 두 가지로 풀 수 있는 문제입니다.

이런문제에서 주의 해야할 점은 딱 하나 정도인데요. 이 답이 나오는 범위를 체크를 해줘야 한다는 점입니다. 

N이 여기서는 100까지로 한정되어 있는데 이 범위가 int의 범위를 벗어나는지를 체크를 해보고 넘어가야됩니다.

이 문제는 dp중에 점화식을 찾기가 쉬운 문제중 하나입니다. 

cache[n] = cache[n-1] + cache[n-5]로 범위는 간단합니다. 

더 쉽게 생각해보면, p(11)이 나오기 위해서는 -> 12길이짜리 삼각형이 나오기 위해서는 9 삼각형 p(10)과 3 삼각형 p(6) 을 더해서 만들어지니. 다시 계산을 해보면, 위와 같은 공식이 나오게됩니다. 

두개를 동시에 보여드리도록 하죠.

Top-down 방식

/* 2019.02.06 dp top-down 형식으로 다시풀기
 * cache[]를 int로 해서 틀렸고 long으로 해야지 맞음
*/
package codeBaekJoon;

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

public class no9461_padovanSequence {
	static int n;
	static long cache[];
	
	static long ps(int x){
		if(cache[x] != -1){
			return cache[x];
		}
		else{
			if(cache[x-1]==-1 && cache[x-5]==-1){
				return cache[x] = ps(x-1)+ps(x-5);
			}
			else if(cache[x-1]==-1){
				return cache[x] = ps(x-1)+cache[x-5];
			}
			else if(cache[x-5]==-1){
				return cache[x] = cache[x-1]+ps(x-5);
			}
			else{
				return cache[x] = cache[x-1]+cache[x-5];
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		cache = new long [105];
		Arrays.fill(cache, -1);
		cache[0] = 0;
		cache[1] = 1;
		cache[2] = 1;
		cache[3] = 1;
		cache[4] = 2;
		cache[5] = 2;
		while(T-->0){
			n = Integer.parseInt(br.readLine());
			if(cache[n]!=-1){
				System.out.println(cache[n]);
			}
			else{
				ps(n);
				System.out.println(cache[n]);
			}
		}
		
	}
}
 

Bottom-Up  방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
	static long cache[] = new long[100];
	static void cacheReset(){
		for(int i=0; i<100; i++){
			cache[i] = -1;
		}
		cache[0]=1;
		cache[1]=1;
		cache[2]=1;
		cache[3]=2;
		cache[4]=2;
	}

	static void wave(int n){
		int i =0;
		int j =4;
		int k =5;
		while(k<n){
			cache[k] = cache[i]+cache[j];
			k++;
			i++;
			j++;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		while(T-->0){
			int N = Integer.parseInt(br.readLine());
			if(N<6){
				cacheReset();
				System.out.println(cache[N-1]);
			}
			else{
				cacheReset();
				wave(N);
				System.out.println(cache[N-1]);
			}

		}
	}
}


 

결국에는 처음에 5까지는 기초 수열이 필요합니다. n-5를 해주기위해서는 어쨌든 5까진 나와야지 그값이 문제가 안생기게 하려면 기본값인 n=5까지는 그값이 저장되어 있어야합니다.