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

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

---

풀이

평소에는 Bottom-Up(for문) 방식을 택하여 많이 풀었는데, 오늘은 Top-Down(재귀) 방식으로 풀었다.

 

1. 테이블 정의 : P(N) = 마지막 정삼각형의 변의 길이

2. 점화식 : d[i] = d[i-1] + d[i-5];

 

나선형으로 도는 삼각형의 값을 하나하나 나열하면서 규칙성을 찾았다.

 

 

cf. 궁금해서 찾아본 다른 풀이
1~3까지의 값만 할당해주고 나머지는 d[i] = d[i-2] + d[i-3] 의 점화식 적용.
필자는 제시된 그림을 보고 직관적으로 풀이했는데,
조금 더 사고하면 효율적인 코드가 도출된다는 깨달음을 얻음.

 

3. 초기값 : d[0] = 1;

d[1]~d[3] = d[0] = 1,

d[4]~d[5] = 2 라고 예외처리를 해주었다.

 

⚠️ 자료형에 주의!

나선형으로 도는 정삼각형이라서 변의 길이가 어마어마하게 길어질 수 있다.

int의 범위를 넘어갈 수 있으므로, 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 n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++) {
            int k = Integer.parseInt(br.readLine());
            bw.write(fn(k)+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
    public static long fn(int k) {
        long[] d = new long[k+1];
        d[0] = 1;
        int i=1;
        while(i<=k) {
            if(i < 4) {
                d[i] = d[0];
            } else if(i > 3 && i < 6) {
                d[i] = 2;
            } else {
                d[i] = d[i - 1] + d[i - 5];
            }
            i++;
        }
        return d[k];
    }
}

---

 

뭔가 뿌듯하다...

그동안 계속 풀이보며 끙끙댔는데 이번엔 엄청 쉽게 풀었다.

실버 3 수준 문제이고, dp라는 것을 알고 풀었기 때문에 빨리 접근법을 구상할 수 있었다.

꾸준히 하면 성장한다는 것을 느꼈다.

 

오늘 보았던 용기나는 문장 첨부한다.

 

작다고만 생각 말고 작은 생각을 매일 키워라.