/ BOJ

BOJ_9461_파도반수열_JAVA

문제 : 파도반수열

링크 : BOJ_9461_파도반수열

접근 방식

삼각형이 나선으로 놓여져있고 변의 과정이고 어쩌고 규칙이 있기는 한데, 그림과 설명을 이용해서 수열을 이해하는것 보다 나열되어있는 숫자를 보고 알아채는 게 더 쉬웠다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

이게 파도반 수열 P(1)부터 P(10)까지이다.

기본값으로 P(1),P(2),P(3)은 1,1,1이다.

P(4) = P(4-3) + P(4-2) = P(1) + P(2) = 1+1 = 2
P(5) = P(5-3) + P(5-2) = P(2) + P(3) = 1+1 = 2
P(6) = P(6-3) + P(6-2) = P(3) + P(4) = 1 + 2 = 3

위의 세 식을 보면 알겠듯이 해당 수열 P(N) = P(N-3) + P(N-2)의 규칙을 가진다.

피보나치와 유사하게 DP로 위 점화식을 풀어나가면 된다.

풀이 방법

  1. 테스트 케이스 수를 읽어와 테스트 케이스 수 만큼 반복한다.

  2. 변수 N에 주어지는 입력값을 저장한다.

  3. dp용 배열을 N+2개만큼 선언한다. +2를 하는 이유는, N에 3 미만의 수가 주어졌을 때 배열의 값을 벗어나지 않게 하기 위함이다.

  4. 시작값을 3부터 N까지 반복하는데, 위의 점화식대로 계산하여 배열에 순차적으로 추가한다.

  5. 모든 반복이 종료된 후 dp배열의 N-1번째 값을 출력한다.

소스 코드


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

public class BOJ_9461_파도반수열 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		// 버퍼드리더로 값 읽어오기
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for (int i = 0; i < T; i++) {

			int N = Integer.parseInt(in.readLine());

			long[] dp = new long[N+2];

			dp[0] = 1;
			dp[1] = 1;
			dp[2] = 1;

			for (int j = 3; j < N; j++) {
				dp[j] = dp[j - 2] + dp[j - 3];
			}

			System.out.println(dp[N - 1]);

		}

	}

}