백준 9461번: 파도반 수열

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

위의 그림과 같이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, ... 순으로 커지는 수열을 P(N)이라고 할 때,

입력받은 N에 대해서 P(N)을 구하는 문제이다.

 

해당 수열을 보다보면 P(N) = P(N - 1) + P(N  - 5)라는 것을 알 수 있다.

그래서 P[1]부터 P[5]까지의 수를 미리 지정해주고 나머지는 식에 맞춰 재쉬함수로 구현하는 것으로 끝날 줄 알았다.

한 번 틀리고 어디가 틀렸을까 고민하다가 혹시 수가 너무 커지는게 아닐까 싶어서

P[N]과 재귀함수의 리턴 값은 long으로 바꿔주니 문제를 풀 수 있었다.

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

public class Main {
  static long[] P = new long[101];
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    String RES = new String();
    int N = Integer.parseInt(br.readLine());
    P[1] = 1;
    P[2] = 1;
    P[3] = 1;
    P[4] = 2;
    P[5] = 2;

    for (int i = 0; i < N; i++) {
      int pn = Integer.parseInt(br.readLine());
      RES += wave(pn) + "\n";
    }
    
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(RES);
    bw.flush();
    bw.close();
  }

  static long wave(int N) {
    if (P[N] != 0) return P[N];
    else P[N] = wave(N - 1) + wave(N - 5);
    return P[N];
  }
}