[9461번] 파도반 수열 JAVA☕

www.acmicpc.net/problem/9461

9461번: 파도반 수열

알고리즘 [접근 방법]

이번 문제는 테스트 케이스가 여러개이므로 각 케이스마다 동적계획법을 사용해야 한다.

 

예를들어 Func()함수가 있다고 가정한다면, 이 함수는 Func(N) = Func(N-1) + Func(N-2)를 만족하는 피보나치 수를 구하는 기능을 담당한다. 이 때 N=4에 대하여 값을 구하고자 하면 아래와 같은 과정을 거칠 것이다.

 

• Func(4) = Func(3) + Func(2)
• Func(4) =  (Func(2) + Func(1)) + Func(2)

이러면 적어도 최소한 N= 1~4 까지는 탐색이 완료되어 값을 찾고 있을 것이다.  만약 이후의 N이 4보다 작거나 같으면 이미 탐색이 완료되었던 값이므로 탐색할 때 얻었던 값을 바로 반환해주면 된다. 반대로 N=7 같이 4보다 큰 수를 탐색하게 되면 다음과 같이 탐색을 거치면 된다.

 

• Func(7) = Func(6) + Func(5) 
• Func(7) =  (Func(5) + Func(4)) + (Func(4) + Func(3))
• Func(7) =  ((Func(4) + Func(3)) + Func(4)) + (Func(4) + Func(3))

이 세가지 과정만 거치면 4와 3에 대해 호출할 때 이미 탐색했던 값이므로 여기까지만 탐색한 뒤 값을 반환하면 된다. 이렇게하면, 주어지는 N의 범위가 1 ≤ N ≤ 100 이더라도 만약 주어지는 수의 최대값이 10인 경우도 있기 때문에 11~100까지 탐색할 필요가 없다는 것이다. 즉, 처음부터 모든 값을 구하는 것보다는 상황에 맞게 필요한 부분만 탐색을 해주는 것이다.

---

이제 파도반 수열에 대해 알아보자면,

P(1)부터 P(10)까지 첫 10개 숫자는 1,1,1,2,2,3,4,5,7,9 이다. 라는 조건에서 보면 쉽게 볼 수 있다. 그림으로 보자면 다음과 같다.

즉, 피보나치와는 조금 다른 점이라면 두 인접 값의 합이 다음 인덱스에 위치하는 것이 아닌 다다음의 인덱스에 위치한다는 것이다.

수식으로 보자면 Func(N) = Func(N-2) + Func(N-3)이다.

파도반 수열의 경우, 100일 때의 값이 9000억 가까이 되기 때문에 int형의 범위를 넘어간다. 그러므로 long 타입으로 해주어야 한다.

static long[] seq = new long[101];	// 배열 비어있는 표시는 -1 이라고 가정
 
seq[0] = 0;
seq[1] = 1;
seq[2] = 1;
seq[3] = 1;
 
long Padovan(int N) {
	if(seq[N] == -1) {	// 해당 배열에 값이 없을경우 재귀호출
		seq[N] = Fib(N - 2) + Fib(N - 3);
 	}
	return seq[N];
}

또는 -1로 초기화 해주는 대신 Long 타입 Wrapper Class로 하여 null 체크로 하자면 다음과 같이도 할 수 있다.

static Long[] seq = new Long[101];
 
seq[0] = 0L;
seq[1] = 1L;
seq[2] = 1L;
seq[3] = 1L;
 
long Padovan(int N) {
	if(seq[N] == null) {	// 해당 배열에 값이 없을경우 재귀호출
		seq[N] = Fib(N - 2) + Fib(N - 3);
 	}
	return seq[N];
}

이 때 변수 초기화 시 L이라는 문자를 붙이거나 (long) 1 이런식으로 캐스팅을 해주어야한다.

---

풀이 및 코드

- 방법 1 : [Scanner + 재귀]

import java.util.Scanner;
 
public class Main {
	
	public static Long[] seq = new Long[101];
 
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		seq[0] = 0L;
		seq[1] = 1L;
		seq[2] = 1L;
		seq[3] = 1L;
		
		int T = in.nextInt();
		
		while(T-- > 0) {
			int N = in.nextInt();
			System.out.println(padovan(N));
		}
		
	}
	
	public static long padovan(int N) {
		if(seq[N] == null) {	// 탐색하지 않은 인덱스일 경우 재귀호출
			seq[N] = padovan(N - 2) + padovan(N - 3);
		}
		return seq[N];
	}
 
}

- 방법 2 : [BufferedReader + 재귀]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	
	public static Long[] seq = new Long[101];
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		seq[0] = 0L;
		seq[1] = 1L;
		seq[2] = 1L;
		seq[3] = 1L;
		
		int T = Integer.parseInt(br.readLine());
		
		while(T-->0) {
			sb.append(padovan(Integer.parseInt(br.readLine()))).append('\n');
		}
		System.out.println(sb);
	}
	
	public static long padovan(int N) {
		if(seq[N] == null) {
			seq[N] = padovan(N - 2) + padovan(N - 3);
		}
		return seq[N];
	}
 
}

- 방법 3 : [BufferedReader + 반복문]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	static long[] seq = new long[101];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		padovan();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < T; i++) {
			sb.append(seq[Integer.parseInt(br.readLine())]).append('\n');
		}
		
		System.out.println(sb);
	}
 
	public static void padovan() {
		
		seq[1] = 1;
		seq[2] = 1;
		seq[3] = 1;
 
		for (int i = 4; i < 101; i++) {
			seq[i] = seq[i - 2] + seq[i - 3];
		}
	}
 
}