Baekjoon/[3] DP

[백준] 1904번 01타일 JAVA (자바) 풀이

Poorm 푸름 2024. 6. 30. 20:43

문제 1904번 (DP)

 : 각각의 타일들은 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으로 나눈 나머지를 출력

 


[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)  보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결 작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization) 타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때 모두 계산해야 답이 나올 때
재귀 반복문
시간 복잡도 O(n) 시간 복잡도 O(n)

 

1.1은 단독 가능 0은 쌍으로만 가능

  • dp[1]의 경우 = 1가지
    • 1
  • dp[2]의 경우 = 2가지
    • 00 / 11
  • dp[3]의 경우 = 3가지 
    • 001 / 100 / 111
  • dp[4]의 경우 = 5가지
    • 0011 / 1100 / 1001 / 1111 / 0000
  • dp[5]의 경우 = 8가지
    • 00001 / 00100 / 10000 / 00111 / 11111 / 11100 / 10011 / 11001 

 

2. 인덱스 예외처리 발생

  • N이 1부터 입력받기 때문에 당연히 dp[1]부터 dp[2]까지만

  • 2가지만 초기화한 이유
    dp 점화식이 2가지 식이 필요하다
    dp[i-1] / dp[i-2]이므로 2개의 식을 초기화 했다

  • dp배열을 new int[N+1]라고 하면 인덱스 예외 발생
    new int[1000001] 으로 초기화해야 에러가 나지 않는다

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[1000001];
        
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=N ; i++){
            dp[i] = (dp[i-1]+dp[i-2])%15746;
        }
        
        System.out.println(dp[N]);
        
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int dp[] = new int[1000001];  dp 배열 초기화
        
 :  dp[1]=1;  1가지
    dp[2]=2;  2가지
        
 :  for(int i=3; i<=N; i++){  이전 인덱스와 그보다 더 이전 인덱스 더해주기
            dp[i] = (dp[i-1]+dp[i-2])%15746; 15746으로 나눈 나머지 저장
    }
        
 :  System.out.println(dp[N]);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)


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

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시