[백준 - 1904번] 01타일 - Java //Wello Horld//

우리 모두 BOJ 의 1904번문제 01타일을 풀어보도록 하자

문제 자체는 무척이나 간단하다

일단 2진 수열을 만드는 문제인데, 0은 없고, 00 만 있는 상황이다

예를들어, 크기 N = 1일 때, (1) 밖에 없으므로 수열의 개수는 1이고,

N = 2 일 때, (11, 00)  으로 수열의 개수는 2개가 된다.

N = 3 일 때, (111, 100, 001) 으로 수열의 개수는 3개가 된다.

매우 간단한 다이나믹 프로그래밍(Dynamic Programming) 문제이다. 

N = 3 일 때, 가능한 수를 보면,

• N = 1 일 때, 가능한 (1) 에다가 00 을 더한 100
• N = 2 일 때, 가능한 (11, 00) 에다가 1을 더한 111, 001

이렇게 3개 이다.

N = 4 일 때도 똑같이

• N = 2 일 때, 가능한 (11, 00) 에다가 00 을 더한 1100, 0000
• N = 3 일 때, 가능한 (111, 100, 001) 에다가 1을 더한 1111, 1001, 0011

이렇게 5개 이다.

성공한 코드는 다음과 같이 작성했다

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

public class sample {
    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());
        long[] dp = new long[N + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= N; i ++){
            dp[i] = (dp[i - 2] + dp[i - 1]) % 15746;
        }
        bw.write(dp[N] + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

문제 : https://www.acmicpc.net/problem/1904