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

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

 

백준 파도반 수열 문제를 해결하기 위해서는 규칙(점화식) 을 찾아내면된다. 

 

---

🌘문제 이해하기

 

• 첫 삼각형은 정삼각형으로 변의 길이가 1
• 정삼각형을 계속 추가하는데 나선의 가장 긴변의 길이가 k라고 했을때 , 그 변의 길이가 k인 정삼각형을 추가한다.
• P(N) 은 나선에 있는 정삼각형의 변의 길이 이다.
• N이 주어졌을 때 P(N)을 구하는 프로그램 작성

---

🌗 문제 자세히보기

 

처음에는 무슨삼격형이야? 무슨 규칙이야 싶은데 하나씩 그려보면된다.

 

순서 : 삼각형 한 변의 길이
1 : 1 
2 : 1 
3 : 1
4 : 2
5 : 2
6 : 3
7 : 4
8 : 5
9 : 7
..

 

1,2,3 번째 순서는 한변의 길이가 1로 고정이고 

4번째부터는 2번째와 1번째의 삼각형의 변의 길이의 합 = 1 + 1 = 2

5번째는 3번째와 2번째의 삼각형의 변의 길이의 합 = 1+1 = 2

6번째는 4번째와 3번째의 삼각형의 변의 길이의 합 = 2+1 = 3 

 

인걸 확인할 수 있다.

점화식으로 dp[i] = dp[i-2]+ dp[i-3] 나타낼 수 있다. 

 

🚨주의해야할 점

1. N이 100 까지 주어지므로 변수타입이 int를 벗어나 long으로 지정

2. N이 1 2, 3 일때의 경우를 놓치면 안된다.

---

🌕최종코드

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));      

        int t  = Integer.parseInt(br.readLine());
        int[] test = new int[t];       

        //테스트 케이스 만큼 입력받기
        for(int i=0;i<t;i++)
        {
            test[i] = Integer.parseInt(br.readLine());
        }

        long[] dp = new long[101];

        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;        

        for(int i=0;i<t;i++)
        {
            int n = test[i];            

            for(int j =1;j<=n;j++)
            {
                if(j>3)
                    dp[j] = dp[j-2] + dp[j-3];
            }

            System.out.println(dp[n]);
        }
    }
}