[BOJ] 9461 파도반 수열 - JAVA

1. 문제

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

9461번: 파도반 수열

그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

위에 색칠된 1이 첫번째 삼각형

---

2. 풀이

같은 계산을 여러번 하지 않도록 하기 위해서

1. 테스트 케이스 바깥에 P배열을 만들었다. 어차피 같은 과정으로 계산하기때문에 가능한 방법이다.
2. P[N]==0일때만 반복을 돌려서 값을 찾아냈다.
3. for문 돌리는 중에도 P[i]에 값이 있다면(P[i]!=0) 이면 continue하고 바로 다음 수를 찾으러 갔다.

import java.io.*;

public class BOJ_9641_파도반수열 {
   public static void main(String[] args) throws IOException {
      BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();

      long[] P = new long[101];

      int T = Integer.parseInt(in.readLine());
      while(--T>=0){
         int N = Integer.parseInt(in.readLine());

         if(P[N]==0) {
            for(int i=1;i<=N;i++){
               if(P[i]!=0) continue;
               if(i<=3) P[i] = 1;
               else P[i] = P[i-2]+P[i-3];
            }
         }

         sb.append(P[N]).append("\n");
      }

      System.out.print(sb);
   }
}

---

3. 결과

항상 ★타입★ 이 중요한 걸 명심할 것 (꼭 max값 테스트해보기!!)

그냥 int로 했다가 오버플로우 나서 음수값 출력된 거 보고 깜짝놀랐다. ㅜㅜ