[Java/백준/DP] 1904번: 01타일

문제

www.acmicpc.net/problem/1904

1904번: 01타일

 

코드

IDE에서는 StackOverflowError가 나오지만 백준에서는 정답 뜨는 마성의 코드...

DP에 대해 감을 잘 못 잡아서 동빈나 유튜브로 미리 공부하고 시작했다.

 

내가 생각한 풀이 방법은

1. Basic case에 대해서 생각한다. (이 코드에선 n이 1, 2일 때) : 재귀함수를 끝내는 역할
2. 값들을 중간 중간 저장해주는 역할의 배열 (dp_arr) : 구한 값을 배열에 저장해주었을 때, 그 값을 다시 부를 일이 생기면 다시 계산하지 않고 배열의 값을 return 해주면 된다. (Memoization)
3. n일 때의 점화식을 귀납적으로 세워본다.

 

n==1일 때,

1의 경우만 가능하다.

 

n==2일 때,

00의 경우와 11의 경우가 있다.

 

점화식이 D[n] = D[n-1] + D[n-2]; 인 이유,

길이가 n인 문자열은 그 전의 단계를 생각해볼 수 있다.

D[n-1]의 경우 1만 붙이면 된다. → 1가지

D[n-2]의 경우 00만 붙이면 된다. 11을 붙이는 것은 위의 D[n-1] 경우에 해당하는 것이다. → 1가지

 

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

class Main{
	static int[] dp_arr = new int[1000001];
	public static int zeronetile(int n) {
		if(n==1)
			return 1;
		if(n==2)
			return 2;
		if(dp_arr[n]!=0)
			return dp_arr[n];
		
		return dp_arr[n]=(zeronetile(n-1)+zeronetile(n-2))%15746;
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		
		sb.append(zeronetile(n));
		
		
		bw.write(new String(sb));
		bw.flush();
	}
}