[P&B] #116 BAEKJOON 9461

백준 9461번 JAVA 파도반 수열

문제 설명

아래 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 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)을 출력한다.

 

나의 문제 풀이 코드

import java.io.*;

public class bj9461 {
    private static long[] P;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        P = new long[101];

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(findPNumber(N) + "\n");
        }

        bw.flush();
    }

    private static long findPNumber(int N) {
        if (N <= 3)
            return 1;

        if (P[N] != 0)
            return P[N];

        P[N] = findPNumber(N - 2) + findPNumber(N - 3);
        return P[N];
    }
}

 

문제 풀이 코멘트

문제 풀이에 앞서 수의 규칙을 찾는 것이 중요합니다.

주어진 순서를 보면, 각 항이 이전 두 항의 합으로 나타내지는 피보나치 수열입니다.

1 = 1

1 = 1

1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 1 = 3

3 + 1 = 4

3 + 2 = 5

4 + 3 = 7

5 + 4 = 9

7 + 5 = 12

9 + 7 = 16

12 + 9 = 21

16 + 12 = 28

따라서, 이 수열의 규칙은 "각 항은 이전 두 항의 합"입니다.

 

재귀 함수만 사용하여 풀 수도 있지만 각 호출에서 두 개의 재귀 호출이 발생하므로 지수 시간 복잡도를 가지게 되고 결과적으로 시간 복잡도는 O(2^N)이 됩니다.

 

정답 코드에서는 동적 프로그래밍의 개념 중 메모이제이션을 사용하여 중복 계산을 피하고, 각 N 값에 대한 결과를 한 번만 계산하고 저장합니다. 이로 인해 시간 복잡도는 O(N)이 됩니다. 즉, 입력 값 N에 비례하여 선형으로 계산 시간이 증가합니다. 이는 효율적인 방법으로 문제를 해결할 수 있으며, 큰 입력 값에 대해서도 빠르게 결과를 얻을 수 있습니다.