99클럽 코테 스터디 29일차 TIL DP(파도반 수열)

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

 

<아이디어>

처음에 이해가 잘 안돼서 P(N)을 쭉 써보다가 규칙을 찾았다.

 

P(1) = 1,

P(2) = 1,

P(3) = 2,

P(4) = 2,

P(5) = 2,

P(6) = P(3) + P(5) = 3,

P(7) = P(2) + P(6) = 4,

P(8) = P(1) + P(7) = 5,

P(9) = P(4) + P(8) = 7,
P(10) = P(5) + P(9) = 9,

P(11) = P(6) + P(10) = 12,

P(12) = P(7) + P(11) = 16

 

작성하다보니 슬슬 규칙이 보이기 시작했다.

혹시 몰라서 문제의 그림을 보며 머릿속으로 그려봤는데 한바퀴를 돌 때까지 규칙이 일정하다는 것을 확인했다.

P(1) ~ P(8) 이후부터는 P(N) = P(N-5) + P(N-1) 이 되었고, 이를 활용해 dp배열을 작성했다.

배열의 크기가 최대 100으로 작았고, 입력의 특성 상 100크기의 배열을 모두 계산한 뒤 필요한 값을 출력하기로 했다.

하지만 제출 후 4%에서 틀렸는데! 문득 자료형?! 하고 생각이 들었고 100을 테케로 넣는 순간 자료형 범위를 넘어감을 확인했다.

int 형에서 long형으로 변경해주고, 100을 넣어 한번 더 확인해본 후 제출하니 통과하였다.

자료형 신경 잘 쓰자!!!!!

 

 

<제출코드>

package Study.Week05;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Day29_BOJ_9461_파도반수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        long[] dp = new long[100];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 2;
        dp[5] = 3;
        dp[6] = 4;
        dp[7] = 5;
        for(int i=8; i<100; i++){
            dp[i] = dp[i-5] + dp[i-1];
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n-1] + "\n");
        }

        System.out.println(sb.toString());
    }
}