[알고리즘 / 백준] 9461 - 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

문제는 위와 같으며, 삼각형이 하나일 때부터 차례로 변의 길이를 살펴보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, ... 순서대로 진행되므로 규칙을 파악하면 n 번째 삼각형의 변의 길이는 (n - 2 번째 삼각형의 변의 길이)와 (n - 3 번째 삼각형의 변의 길이)를 더한 값이 됩니다.

 

총 삼각형의 개수가 100개가 최대이므로 처음부터 100개의 배열을 생성하고 각 인덱스에 해당하는 개수의 삼각형의 변의 길이를 저장한 뒤 테스트 케이스에서 입력 받은 수의 값을 찾으면 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

result = [1 for _ in range(101)]
for i in range(4, len(result)):
    result[i] = result[i - 2] + result[i - 3]

t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    print(result[n])

 

자바 코드는 다음과 같습니다. 자바의 경우 100개의 배열에 값을 저장할 때 int 로 하면 범위를 벗어나기 때문에 long 타입의 배열을 사용하였습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long[] result = new long[101];
        for (int i = 1; i < result.length; i++) {
            if (i < 3) {
                result[i] = 1;
            } else {
                result[i] = result[i - 2] + result[i - 3];
            }
        }

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(result[n]);
        }
    }
}