[백준][JAVA알고리즘]9461번 풀이(파도반 수열) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 9461번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 9461 (파도반 수열)

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

 

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

제한

시간제한 : 1 초 (추가 시간 없음)

입력 예시

2
6
12

출력 예시

3
16

성공 코드

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

public class Main {

	static int N ;
	static long[] one;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < N ; i++) {
			int num = Integer.parseInt(br.readLine());
			one = new long[num];
			
			sb.append(wave(num-1)).append("\n");
		}
		
		System.out.println(sb);

}
	public static long wave(int n) {
		if(one[n] != 0)
			return one[n];

		if(n==0 || n==1 || n==2)
			return one[n]=1;
		
		return one[n] = wave(n-2) + wave(n-3);
		
	}
}

파도반 수열 알고리즘에서 또한 패턴을 찾아 메모 이제이 션 기법을 이용하는 문제였습니다. 사실 패턴 찾기야 굉장히 쉽습니다. 혹시 메모이제이션기법이 무엇인지 모르시면 아래 글을 간략히 읽고 오시면 됩니다.(STEP1)

 

[백준][JAVA알고리즘]9184번 풀이(신나는 함수 실행) - 초보도 이해하는 풀이

 

이번 문제는 조금 문제를 푸실 줄 아시면 굉장히 쉬운 문제였다고 볼 수 있습니다.

그럼 이제 STEP을 따라가면서 간략히 이해시켜드리겠습니다.

---

알고리즘 흐름도

입력받기 -> 받은 입력은 반복하여 몇 번째 삼각형인지 입력받기 -> 재귀를 이용하여 값 찾기 (단 메모 이제이 션 사용) -> 출력하기

---

STEP1 패턴 찾기

 패턴은 굉장히 쉽습니다. 기존에 많이 보였던 피보나치수열과 굉장히 유사한 모습을 보여주도 한번 쭉 나열해 보도록 하죠

1
1
1
2
2
3
4
5
7
9
12
16

16 = 9 + 7

12 = 7 + 5

9 = 5 + 4

네 이게 바로 규칙입니다.

 

n = (n-2) + (n-3)

사실 이 규칙만 찾으면 굉장히 쉽게 풀이가 가능하죠

---

STEP2 찾은 패턴으로 재귀 사용하기

public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < N ; i++) {
			int num = Integer.parseInt(br.readLine());
			one = new long[num];
			
			sb.append(wave(num-1)).append("\n");
		}
		
		System.out.println(sb);

}

입력을 받는 방법은 간단합니다. 여기서 왜 one이 long배열인가 하는 점은 바로 STEP 3에서 알려드리겠습니다.

이런 식으로 wave라는 함수에 넣어줍니다.

(wave는 재귀 함수)

 

	public static long wave(int n) {
		if(one[n] != 0)
			return one[n];

		if(n==0 || n==1 || n==2)
			return one[n]=1;
		
		return one[n] = wave(n-2) + wave(n-3);
		
	}

아주아주 간단합니다! 하나씩 알려드리겠습니다.

 

 - 첫 번째 if문

메모이제이션기법을 활용하기 위한 조건문입니다. 해당 배열에 값이 0이 아니라는 소리는 이미 계산한 어떠한 값이 들어있음을 의미합니다. 그렇기 때문에 더 이상 재귀를 돌리지 말고 바로 해당 값은 반환해 주어 시간을 단축시키는 역할을 합니다.

 

 - 두 번째 if문

 기본적으로 0 1 2 즉, 1, 2, 3번째 삼각형을 지정해 주어야 합니다. 물론 조건은 n < 3으로 해주어도 상관은 없고요. 왜 저렇게 설정하느냐 반환하는 값을 보면 n-3까지 갑니다. 만약 3보다 작은 값을 걸러주지 않으면 인덱스가 음수가 돼버려 downflow가 발생하게 됩니다. 따라서 그 하위 값들은 임의로 지정해주어 오류를 없애줍니다..

 

 - 마지막 return

핵심이자 재귀의 방법이죠. 해당 번째의 인덱스 (즉, 몇 번째 삼각형인가)에 -2 // -3번째 값을 더해주어 반환해 주면 끝!

 

아직도 이해가 되시지 않으시는 분들을 위하여 하나의 예제로 풀어드리겠습니다.

6과 12로 보여드리죠

 

 6이 들어왔을 경우

1, 2번 if문에 걸리지 않죠.

return one [5] = wave(3) + wave(2) 이렇게 반환되어야 합니다. 

 

wave(3)에 경우  1, 2번 if문에 걸리지 않습니다.

wave(2)의 경우 2번 if문에 걸리게 됩니다.

wave(3) => return one [3] = wave(1) + wave(0)

wave(2) => return one [2] = 1

네 이제 wave(0),  wave(1), wave(2)는 2번째 if문에 걸리게 되죠. 1을 반환합니다.

그럼 이제 각각 값을 넣어주면 됩니다.

 

wave(3) = 1 + 1

wave(2) = 1

 

견과론 적으론 one [5] = 2 + 1 즉, 3을 반환해 줍니다. 그렇게 해당 6 값을 계산하고 나면

one [] 배열에는 해당 값들이 들어가 있겠죠

one [0] = 1

one [1] = 1

one [2] = 1

one [3] = 2

one [5] = 3

 

다음에 12의 값이 들어온다면, 만약 해당 값을 찾기를 원하게 된다면, 바로 배열에서 해당 값을 꺼내오는 것으로 재귀를 줄일 수 있답니다.

 

---

STEP 3 숨은 오류 찾기

 숨은 오류라 하면 앞서 설명한 long입니다. N이 문제에서 주어진 것처럼 100까지의 수가 들어가게 됩니다. 그러나 INT로 지정할 시 INT가 담을 수 있는 정수의 숫자를 넘어가기 때문에 반듯이 더 큰 정수를 담을 수 있는 변수로 선언해 주어야 오류가 나지 않습니다 ~

---