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

백준 9461번 문제 - 파도반 수열

9461번: 파도반 수열

---

문제 분석 

 

 

• 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다.
• 삼각형을 높는 방법
  • 첫 삼각형은 정삼각형으로 변의 길이는 1이다.
  • 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.
  • 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
• 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.
• N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
  • P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

---

해결 포인트

 

• DP로 풀이
• 정해져있는 dp 값
  • dp[1] = dp[2] = dp[3] = 1
  • dp[4] = dp[5] = 2
• 이후 dp의 규칙을 찾아보기

1 = 1
2 = 1
3 = 1
4 = 2
5 = 2
6 = 3 = p5 + p1
7 = 4 = p6 + p2
8 = 5 = p7 + p3
9 = 7 = p8 + p4
10 = 9 = p9 + p5
11 = 12 = p10 + p6
12 = 16 = p11 + p7
13 = 21 = p12 + p8

• dp의 규칙 : N = p[N-1] + p[N-5]
• dp[100]은 큰 값  ! - Long 사용 
  • 이걸 몰라서 좀 해맸다. 앞으로 가장 마지막 값을 확인하는 습관, 혹은 Long 을 사용하는 습관을 가져야겠다.

---

코드

 

import java.io.*;

public class Main {
    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());

        long [] dp = new long[101];
        dp[1] = dp[2] = dp[3] = 1;
        dp[4] = dp[5] = 2;
        for (int i = 6; i <= 100; i++) {
            dp[i] = dp[i-1] + dp[i-5];
        }

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());

            bw.write(dp[N] + "\n");
        }
        bw.flush();
        bw.close();
    }
}