백준/1904 01타일 / 다이나믹 프로그래밍 + 제출전 최악의경우값들 넣어보기 + dp배열의 크기는 나올수있는 최대값으로 잡기

01타일 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.75 초 (추가 시간 없음)

256 MB

75477

24571

19491

31.851%

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력 1 복사

4

예제 출력 1 복사

5

 

---

풀이

/**
 * N=1 일때 경우의 수 1개
 * N=2 일떄 경우의수 2개
 * N=3 일때 경우의 수 3개
 * N=4 일때 경우의 수 5개
 * N=5 일때 경우의 수 8개
 * 규칙을 살펴보면 점화식 f(n) = f(n-2) + f(n-1)가 됨을 알 수 있다.
 * 다이나믹프로그래밍을 이용하여 문제를 풀어보자.
 */

n이 1~1000000인데

1을 넣고 테스트를 안해봐서 인덱스오류가 발생했었다.

제출하기전에 양쪽끝값을 넣어보는 습관을 들이자.

 

하지만 memoization을 진행할때 최대값의 크기를 가진 dp배열을 생성해서 사용하자.

아래코드로 수정

아래코드로 수정했을때 장점 -> dp배열을 전역변수로 지정해놨기에 재활용가능 , 즉 테스트케이스가 여러개일때 연산수를 줄일 수 있음 + n이 1일때의 인덱스오류를 걱정안해도된다.

 

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    /**
     * N=1 일때 경우의 수 1개
     * N=2 일떄 경우의수 2개
     * N=3 일때 경우의 수 3개
     * N=4 일때 경우의 수 5개
     * N=5 일때 경우의 수 8개
     * 규칙을 살펴보면 점화식 f(n) = f(n-2) + f(n-1)가 됨을 알 수 있다.
     * 다이나믹프로그래밍을 이용하여 문제를 풀어보자.
     */

    static int n;
    static int[] memoization = new int[1000001];
    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
    }

    static void solve() throws IOException {
        bottomUp(n);
        bw.write(memoization[n]+"");
    }

    static void bottomUp(int n) {
        memoization[1] = 1;
        memoization[2] = 2;

        for (int i = 3; i <= n; i++) {
            if (memoization[i] == 0) {
                memoization[i] = (memoization[i - 2] + memoization[i - 1]) % 15746;
            }
        }
    }

}

 

 

 

 

 

원래코드 ( dp배열의 크기를 지정해주지않았음)

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    /**
     * N=1 일때 경우의 수 1개
     * N=2 일떄 경우의수 2개
     * N=3 일때 경우의 수 3개
     * N=4 일때 경우의 수 5개
     * N=5 일때 경우의 수 8개
     * 규칙을 살펴보면 점화식 f(n) = f(n-2) + f(n-1)가 됨을 알 수 있다.
     * 다이나믹프로그래밍을 이용하여 문제를 풀어보자.
     */

    static int n;
    static int[] memoization;

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        if (n == 1) {
            System.out.println(1);
            System.exit(0);
        }
        memoization = new int[n+1];
    }

    static void solve() throws IOException {
        bottomUp(n);
        bw.write(memoization[n]+"");
    }

    static void bottomUp(int n) {
        memoization[1] = 1;
        memoization[2] = 2;

        for (int i = 3; i <= n; i++) {
            if (memoization[i] == 0) {
                memoization[i] = (memoization[i - 2] + memoization[i - 1]) % 15746;
            }
        }
    }

}