[JAVA] 백준 1904 01타일

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

1904번: 01타일

 

 

 

문제 풀이 

 

- "00"타일과 "1"타일로 만들 수 있는 이진수의 가짓수를 찾는 문제 

- 1타일과 00타일을 이전의 타입의 붙이는 문제이므로 메모이제이션을 이용한 동적계획법으로 풀이 

 

n=1 일때 1

n=2 일때 00,11 

n=3 일때 001,111,100

n=4 일때 0000,1100,0011,1111,1001

n=5 일때 00001,11001,00111,11111,10011,00100,11100,10000

 

- 타일의 가짓수는 피보나치 수열의 패턴을 보임 

- memo[n] = memo[n-1]+memo[n-2]의 점화식을 사용하여 문제를 풀 수 있음

 

- n이 1인 경우 ArrayIndexOutOfBounds 에러 발생하기 때문에 예외 처리 필요 

 

 

정답

 

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

public class Main {
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        int n = Integer.parseInt(br.readLine());
        int memo[] = new int[n+1];
        
        
        memo[1] =1;
        
        if(n>1)
        {
        	memo[2]=2;
        }
        
        for(int i=3; i<=n; i++)
        {
        	memo[i] = memo[i-1]+memo[i-2];
        	memo[i]%=15746;
        }
        
        bw.write(memo[n]+"");
        
        bw.flush();
        bw.close();
   
       
    }
}