[백준 9461번 파도반 수열]

728x90

오늘의 문제는 파도반 수열이다.

 

 

 

처음엔 무조건 완전탐색!

 

이 문제는.. 보고 규칙성을 찾아야만 할 것 같았다.

처음에는 많이 헤맸지만..!

찾았다 빈틈의 실..!

P(6) 이후인 P(N)들은 그 값이 P(N-1) + P(N-5)라는 사실을 알게되었다.

그리고 N의 범위는 ( 1 <= N <= 100 )이기 때문에 매번 구해주기 보다는

아예 길이가 100정도인 배열을 선언해 해당 idx의 값들을 구해주고 출력만 하도록 코드를 작성하였다.

 

코드는 다음과 같다.

( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

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();
        int T = Integer.parseInt(br.readLine());
        //수들이 더해지다보면 상당히 커진다.. 이때문에 2번이나 틀렸다 ㅎ 확인 또 확인..
        long [] arr = new long [110]; 
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        arr[4] = 2;
        arr[5] = 2;
        //[5]번까지는 규칙성을 찾지 못했다 !! 그래서 한땀 한땀 넣어주며 ,,
        //있다면 알려주세요 ..
        //아 그리고 편의성을 위해 1부터 넣었고 넉넉한 idx를 위해 110까지 해줬습니다 !
        
        //나머지 idx들도 채워주도록 하자.
        for(int i = 6; i<110; i++){
            arr[i] = arr[i-1] + arr[i-5];
        }

        int num;
        for(int tc = 0; tc<T; tc++){
            num = Integer.parseInt(br.readLine());
            sb.append(arr[num]).append("\n");
        }
        System.out.println(sb);
    }
}

 

처음에 바보같이 int의 범위를 벗어난줄 모르고 급하게 풀다가 문제도 잘못봐서 완전... 

산으로 가는 풀이로 풀었었다 ㅎ ( 물론 int범위 아니어서 틀렸음ㅋ )

그때는 왜 최대 범위인 100을 안넣어봤나 모르겠다 .. 바로찾았을텐데 그럼 ㅠ

int, long 범위는 조심 또 조심하길 바라며 ,,!

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

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