Baekjoon | Q.9461 - 파도반 수열

9461번: 파도반 수열

 동적 프로그래밍을 활용하여 점화식을 해결하는 문제이다.

import java.util.Scanner;

public class Main {
  static long[] memory;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int t = sc.nextInt();

    for (int i = 0; i < t; i++) {
      memory = new long[101];
      memory[1] = 1;
      memory[2] = 1;
      memory[3] = 1;
      memory[4] = 2;
      memory[5] = 2;

      int n = sc.nextInt();
      sb.append(P(n) + "\n");
    }

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

  static long P(int n) {
    if(memory[n] != 0) return memory[n];

    return memory[n] = P(n-1) + P(n-5);
  }
}

처음에 자료형을 int로 결과값을 저장했더니 틀렸다. 결과값을 long으로 저장해주자. 문제의 점화식은 P(n) = P(n-1) + P(n-5)이다. 처음 초기값 P(1) 부터 P(5) 까지는 설정해주고 그 이후는 점화식을 이용하여 재귀 함수를 이용하여 풀어주었다. 이 때, 한번 해결한 문제는 다시 재귀호출을 하지 않기 위해 배열에 저장해주었다.