[백준] 9461번 - 파도반 수열 [Java]

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

 

[백준] 9461번 - 파도반 수열 [Java]

---

1.  아이디어

 

다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

파도판 수열에서 두 가지 점화식을 얻을 수 있었는데 먼저 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 이렇게 이어지는 규칙성에서 a(n) = a(n-2) + a(n-3)을 얻을 수 있고, 특정 삼각형의 한 변이 이전 삼각형의 두 변으로 이루어졌다는 점에서 a(n) = a(n-1) + a(n-5)를 얻을 수 있다. 두 가지 방식 중 좀 더 직관적인 두 번째 방식으로 구현했다. 첫번째 방식도 a(n-3)번 삼각형을 대칭이동 시키면 두 선분의 길이가 같은 걸로 확인할 수 있지만 조금 어색한 것 같았다.

---

3. 코드

 

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));
        StringBuilder sb = new StringBuilder();

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

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

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기