백준 9461번: 파도반 수열

문제 설명

• https://www.acmicpc.net/problem/9461
• 일정한 규칙을 찾는 문제입니다.

접근법

• 10번째수부터 거꾸로 보면 규칙을 더 빨리 발견할 수 있습니다.
  • 초기조건인 [1,1,1,2,2]에서는 뚜렷한 규칙이 없습니다.
• 
• 숫자가 커지기 때문에 int가 아닌 long으로 문제를 풀어야 합니다.
• dp는 memoization을 습과화 하는게 좋습니다.

pseudocode

func(){
	if(N이 1~5이면){
    	넣어둔 값을 그대로 사용합니다.
    }else{ // N이 6이상의 값이면
    	if(아직 배열에 값이 채워지지 않았다면){
        	arr[N] = func(N-1) + func(N-5); // 점화식으로 값을 구합니다.
        	return arr[N];
        }else{ // 배열에 값이 채워져 있다면 == 이전에 구한적 있는 값이라면
        	return arr[N]; // 재귀적으로 구하지 않고 저장해둔 값을 바로 씁니다.
        }
    }
}

문제 풀이

import java.util.*;

class Main {
	static long[] arr = new long[101];
	public static void main(String[] args) {
		arr[1] =1;
		arr[2] =1;
		arr[3] =1;
		arr[4] =2;
		arr[5] =2;
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			System.out.println(func(sc.nextInt()));
		}
//		func(100);
//		System.out.println(Arrays.toString(arr));
	}
	
	public static long func(int N) {
		if(N <= 5) {
			return arr[N];
		}else {
			if(arr[N] == 0) {
				arr[N] = func(N-1)+func(N-5);
				return arr[N];
			}else {
				return arr[N];
			}
		}		
	}
}