알고리즘 공부

Baekjoon | Q.9461 - 파도반 수열

치킨닮은닭 2020. 6. 9. 01:01
 

9461번: 파도반 수열

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 �

www.acmicpc.net

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

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) 까지는 설정해주고 그 이후는 점화식을 이용하여 재귀 함수를 이용하여 풀어주었다. 이 때, 한번 해결한 문제는 다시 재귀호출을 하지 않기 위해 배열에 저장해주었다.