알고리즘/백준
[백준 9461번 파도반 수열]
익명의 문과 개발자
2024. 7. 10. 19:05
728x90
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
728x90