[알고리즘/백준] 1904번 : 01타일(Java)

문제	1904번 : 01타일
문제링크	https://www.acmicpc.net/problem/1904
난이도	S3
언어	Java
분류	DP | 다이나믹 프로그래밍

 

 

📌 최종 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	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());
		
		bw.write(String.valueOf(fn_dp(n)));
		
		bw.flush();
		bw.close();
	}
	
	public static int fn_dp(int n) {
		int value = 0;
		
		int a = 1;
		int b = 2;
		if(n <= 2) {
			return n;
		}
		else {
			for(int i = 3; i <= n; i ++) {
				value = (a + b) % 15746;
				a = b;
				b = value;
			}
		}
		return value;
	}
}

📌 구해야 하는 정답

 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지

📌 풀이하기

1. 입력받기

// 만들 수 있는 길이
int n = Integer.parseInt(br.readLine());

 

2. 계산

public static int fn_dp(int n) {
    int value = 0;

    int a = 1;
    int b = 2;
    if(n <= 2) {
        return n;
    }
    else {
        for(int i = 3; i <= n; i ++) {
            value = (a + b) % 15746;
            a = b;
            b = value;
        }
    }
    return value;
}

 

3. 결과 출력

bw.write(String.valueOf(fn_dp(n)));

 

 

📌 시간 복잡도

DP 배열을 탐색하는 시간복잡도를 구해봅시다.

점화식을 계산하는데에는 단순 상수연산이 소요됩니다 → O(1)

이를 총 N개에 대해 탐색하므로, 최종 시간복잡도는 O(N)이 됩니다.

N은 최대 1,000,000이므로 시간제한 0.75초안에 충분히 가능한 연산 개수 입니다.

 

📌 코드 설계

1. 문제의 input을 받습니다.
2. DP의 초기값을 설정합니다.
3. 세운 점화식에 따라 dp 배열을 탐색합니다.
4. 정답을 출력합니다.

 

처음에 문제에 지시한 15746으로 나눈 나머지를 하지 않아 틀렸다.. ㅎ

이전에 풀었던 피보나치를 적용한 문제였다.

2025.04.23 - [알고리즘] - [알고리즘/백준] 2747번 : 피보나치 수(Java)

[알고리즘/백준] 2747번 : 피보나치 수(Java)