파도반 수열(9461)

피보나치 수와 비슷한 규칙을 찾아 동적 계획법으로 푸는 문제

문제

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

예제 입력

2
6
12

예제 출력

3
16

동적 트래킹을 위해 만든 배열은 int로 생성해서 풀어가고 있었는데 계속 틀렸다고 하길래 검색해보니까

이번 수열은 만약 100이 되는 경우 9000억을 넘어간다고한다! 그러면 int형의 범위를 벗어나기 때문에 long을 사용한다고 한다

int형의 범위는 2,147,483,647이다. 즉 21억이 int형의 한계가 되겠다!

풀이

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

public class Main{
    static long arr[] = new long[101];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        wave();
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++){
            int tmp = Integer.parseInt(br.readLine());
            sb.append(arr[tmp]).append('\n');
        }

        System.out.println(sb);
    }

    public static void wave(){
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        for (int i = 4; i < 101; i++) {
            arr[i] = arr[i-2]+arr[i-3];
        }
    }

}

이렇게 반복문을 활용한 방법도 있고

재귀를 활용하는 방법도 있다.

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

public class Main{
    static long arr[] = new long[101];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;

        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++){
            int tmp = Integer.parseInt(br.readLine());
            sb.append(wave(tmp)).append('\n');
        }

        System.out.println(sb);
    }

    public static long wave(int n){
        if(arr[n] == 0){
            arr[n] = wave(n-2)+wave(n-3);
        }
        return arr[n];
    }

}

백준

두번째 시도

왠만하면 재귀보다는 배열을 활용하는 방법을 사용해서 풀게 된다.

import java.io.*;
public class Main{
    static long[] arr = new long[101];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++){
            int t = Integer.parseInt(br.readLine());
            fn(t);
            bw.write(arr[t] + "\n");
        }

        bw.flush();
    }

    public static void fn(int n){
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        for(int i=4; i<101; i++){
            arr[i] = arr[i-2]+arr[i-3];
        }
    }
}