[JAVA] BOJ(백준) - 파도반 수열 - 9461

문제 내용

https://www.acmicpc.net/problem/9461

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)을 출력한다.

 

---

문제 접근 방법

수열을 10번째까지 써줬기 때문에 우리는 규칙을 찾고 식을 만들기만 하면된다.

 

수를 잘보면 피보나치와 비슷하게 f(n) = f(n-2) + f(n-3) 이라는 규칙이 생기는걸 알 수 있다.

그리고 이 규칙을 활용하면

 

TopDown(재귀)방식과 ButtomUp(for문)방식으로 문제를 해결할 수 있다.

 

dp배열에서 입력받은 N은 인덱스가 되고 할당되는 값은 N번재일때 P(N)이 된다.

즉, 1차원 배열로 생성해야 하고, 배열의 크기는 TestCase마다 N+1의 크기로 설정할수도 있겠지만 그러면 배열을 테스트케이스마다 계속 다시 생성하고, 첫번째부터 다시 계산해서 저장해놔야하는 번거로움이 생긴다.

 

따라서 dp 배열은 전역변수로 설정하여 크기를 N의 최대길이로 설정해준다.

 

주의해야 할점은 문제를 구현하고 N의값을 1과 100을 넣어보면 알겠지만 N이 100일 경우 8900억 정도에 가까운 수가 생성되기 때문에 DP배열의 타입을 long으로 설정해줘야 한다.(int 타입으로는 담을수가 없음)

 

풀이를 보자.

 

---

풀이

재귀(TopDown)

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

/*
 *	재귀 
 */
public class BOJ_9461_1 {
	static long[] dp = new long[101];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			int N = Integer.parseInt(br.readLine());
			
			dp[0] = 0;
			dp[1] = 1;
			dp[2] = 1;
			dp[3] = 1;
			dp[4] = 2;
			dp[5] = 2;
			long result = padoban(N);
			sb.append(result).append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	public static long padoban(int n) {
		if(dp[n]!=0) {//저장(계산)된 값은 바로 반환
			return dp[n];
		}
		dp[n] = padoban(n-2) + padoban(n-3);
		return dp[n];
	}
}

---

for문(DP 배열사용)

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

/*
 * for문 DP배열 사용
 */
public class BOJ_9461_2 {
	static long[] dp = new long[101];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			int N = Integer.parseInt(br.readLine());
			if(N<=3) {//N이 3이하일땐 무조건 1임.
				sb.append(1).append("\n");
				continue;
			}
			dp[1]=1;
			dp[2]=1;
			dp[3]=1;
			//아래부터 N까지 계산값 전부 저장.
			for(int j=4; j<=N; j++) {
				dp[j] = dp[j-2] + dp[j-3];
			}
			sb.append(dp[N]).append("\n");
		}
		
		System.out.println(sb.toString());
	}
}

 

for문(DP배열 미사용)

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

/*
 * for문 DP배열 미사용
 */
public class BOJ_9461_3 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			int N = Integer.parseInt(br.readLine());
			if(N<=3) {//N이 3이하일땐 무조건 1임.
				sb.append(1).append("\n");
				continue;
			}
			
			long f = 0;
			long f1 = 1; //f(n-2)
			long f2 = 1; //f(n-3)
			long f3 = 1; //f(n-1)
			
			for(int j=3; j<N; j++) {
				f = f1+f2;
				f2 = f1;
				f1 = f3;
				f3 = f;
			}
			sb.append(f).append("\n");
		}
		
		System.out.println(sb.toString());
	}
}

 

---

마무리

이번 문제는 3가지 풀이로 풀어봤다. 어렵게 느껴진 문제는 아니였고 슬슬 풀리기 시작해서 그런지 처음에 DP에 대해 막연했던 생각이 차츰 정리되는 기분이다.