[백준/JAVA] 9461번: 파도반 수열

🔺 문제

9461번: 파도반 수열

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // DP 배열 채우기
        long[] P = new long[101];
        P[1] = P[2] = P[3] = 1;
        for(int i = 4 ; i <= 100 ; i++) {
            P[i] = P[i - 3] + P[i - 2];
        }
        
        // 입력 
        int T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            int num = Integer.parseInt(br.readLine());
            sb.append(P[num]).append("\n");
        }
        
        System.out.println(sb.toString());
        br.close();
    }
}

✅ 해결 아이디어
✔ DP
- P[N] : 나선에 있는 정삼각형의 변의 길이
- 점화식 : P[ i ] = P[ i - 3 ] + P[ i - 2 ]

또 다른 점화식은 P[i] = P[i - 1] + P[i - 5] 라고 함.

 

💥 유의사항

• 100번째 항 요청 시, int형 범위를 넘기므로 배열을 long형으로 만들어야 값이 제대로 나온다. (참고1, 참고2)

 

---

🔺 다른 풀이들

- 복습용... 좋은 설명

[백준] 9461번 : 파도반 수열 - JAVA [자바]

 

- 그림 과정

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

---

💬 느낀 점

앞으로 이 문제 나오면 DP & 점화식 기억해둬야지...

 

 

1회독	2회독	3회독	4회독	5회독
V