[백준] 9461번 : 파도반 수열 - JAVA [자바]

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

---

• 문제

 

 

 

 

그동안 배웠던 동적계획법을 응용하여 써보려 한다. 정석적인 방법과 단순 반복문으로 풀이하는 방법 모두 보여줄 것이다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

그동안의 동적계획법 문제는 테스트 케이스가 1개뿐으로 해당 값에 대한 재귀 또는 반복문으로 풀었었다.

 

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

 

예로들어 Func() 함수가 있다고 가정하자. 이 함수는 Fucn(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 이런식으로 캐스팅을 해주어야 한다.

 

필자의 경우는 Long 이 쓰기 편해서 Long타입으로 쓰고자 한다. (다만 메모리가 적거나 N의 범위가 매우 클 경우에는 Long이 아닌 long 타입으로 해주는 것이 좋다. Long의 경우 객체인지라 일반 자료형에 비해 메모리 차지량이 3배정도 더 많다.)

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

먼저 동적계획법의 의도에 맞게 Top-Down(재귀)방식에 메모이제이션을 이용한 정석적인 풀이 방법으로 위에서 설명한 방법을 사용하여 풀어 볼 것이다. 재귀 알고리즘에 입력방법을 달리하여 풀어보고 다음으로는 반복문을 사용하여 동적계획법을 풀이하는 방법을 보여줄 것이다.

 

정리하자면 다음과 같은 3가지 방법을 사용할 것이다.

 

1 . Scanner + 재귀

2. BufferedReader + 재귀

3. BufferedReader + 반복문

 

 

 

 

---

• 풀이

- 방법 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];
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

물론 long[] 배열로 해도 된다. long 배열을 사용한 방법을 보고싶다면 아래 더보기를 눌러 보시길 바란다.

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);
		
		for(int i = 0; i < 101; i++) {
			seq[i] = -1;
		}
		seq[0] = 0;
		seq[1] = 1;
		seq[2] = 1;
		seq[3] = 1;
		
		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] == -1) {	// 탐색하지 않은 인덱스일 경우 재귀호출
			seq[N] = padovan(N - 2) + padovan(N - 3);
		}
		return seq[N];
	}

}

 

 

어렵지 않게 풀 수 있을 것이다. 가끔 다른 글들을 찾아보면 탐색하지 않은 경우를 조건으로 하지 않고, 무조건 탐색. 즉 백트래킹 방식으로 하시는 분들이 있는데, 이는 동적계획법의 취지와 맞지 않기도 하고 효율도 급격하게 떨어진다.

 

 

---

- 방법 2 : [BufferedReader + 재귀]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 또한 출력에서 조금이나마 시간을 아끼기 위해 StringBuilder 을 추가하여 사용하였다. 

 

 

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 + 반복문]

 

 

 

이 방법도 동적계획법이다. seq[] 배열이 메모이제이션을 해주는 역할을 하고 반복문(Bottom-Up)방식으로 풀어나가는 방식이다.

 

 

 

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];
		}
	}

}

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 21414824  -  방법 3 : BufferedReader + 반복문

채점 번호 : 21414820  -  방법 2 : BufferedReader + 재귀

채점 번호 : 21414819  -  방법 1 : Scanner + 재귀

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

---

• 정리

 

근래 필자가 조금 바쁜 일이 있어서 포스팅을 요 며칠간 업로드하지 못했다.. 🥕🥕🥕  (죄송합니다..)

필자가 보니까 생각보다 동적계획법에서 어려움을 겪는 분들이 꽤 계신 것 같다. 블로그를 운영하시거나 해보시는 분들은 알겠지만 각 포스팅마다 조회수가 뜨는데, 포스팅 기고 기간 대비 동적계획법이 의외로 조회수가 높다는 것이 이를 증명하는 것이 아닐까..

 

만약 동적계획법에 대해 잘 이해가 되지 않는다면 필자가 올린 동적계획법 카테고리의 첫 글부터 정독해보시는 것도 나쁘지 않을 것 같다.

 

별개로 그냥 해보는 말이긴 하지만 요즘 장마철인 것은 아는데 비가 많이 와도 너무 많이 온다.. 참고로 이번달부터 월 1~2회씩 처음 언어를 접하거나, 프로그래밍 관련 수업을 듣는 학생 또는 신입생들을 위한 프로그래밍 언어에 대한 기본 접근방법을 업로드 하고자 한다. 프로그래밍 언어의 한 종류를 배운다기 보단 학습 방법, 분야, 접근법 등과 함께 인문학적 요소(?)들을 가미하여 올리고자 하니 많은 관심을 주시면 감사하겠다.