[JAVA] 백준 9461번: 파도반 수열

 

---

문제

• 파도반 수열이 주어질 때, N번째 삼각형의 변의 길이를 구하는 문제.

 

아이디어

• 문제에 답이 나와있다.
• 변의 길이는 각각 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 인데, 이를 자세히 보면 아래 규칙을 찾을 수 있다.

$$a_{n} = a_{n-2} + a_{n-3}$$

• 이 규칙을 배열을 이용해 그대로 구현한다.

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 합한 값이 int 최대 범위를 넘길 수 있으므로 long 타입으로 선언
        long[] arr = new long[101];
        
        // 초기값 초기화
        arr[1] = arr[2] = arr[3] = 1;
        
        // 미리 100번째 변까지 구함
        for(int i=4; i<101; i++) {
            arr[i] = arr[i-3] + arr[i-2];
        }

        int T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; t++) {
            sb.append(arr[Integer.parseInt(br.readLine())]).append('\n');
        }
        System.out.println(sb);
    }
}

 

 

채점 결과

9461번 채점 결과

기타

• 합한 값이 21억을 넘겨 오버플로우가 발생할 수도 있다는 사실을 간과했다.... 정신 차리자.

 

문제 링크

• 9461번: 파도반 수열 (acmicpc.net)