백준 1904. 00타일

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

 

나의 풀이

첫 번째: 백트래킹으로 풀어 보았다. N이 작을 때는 잘 작동했지만, N이 10 이상으로 커지니 아니나다를까 스택오버플로우가 발생했다.

package test;

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

public class test115 {
	static ArrayList<String> binaryNums;
	static ArrayList<Integer> possibleNum;
	static int N;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		binaryNums = new ArrayList<>();
		possibleNum = new ArrayList<>();
		findPossibleBinaryNum(0);
		System.out.println(binaryNums.size() % 15746);
		bw.close();
		br.close();
	}

	static void findPossibleBinaryNum(int cnt) {
		// cnt 값이 N 넘으면 반환
		if (cnt == N + 1) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < possibleNum.size(); i++) {
				sb.append(String.valueOf(possibleNum.get(i)));
			}
			System.out.println("현재 완성된 경우의 수 = " + String.valueOf(sb));
			binaryNums.add(String.valueOf(sb));
			return;
		}
		// N이 될 때까지 배열에 0 또는 1을 추가
		if (N - cnt >= 2) {
			possibleNum.add(0);
			possibleNum.add(0);
			cnt += 2;
			findPossibleBinaryNum(cnt);
			possibleNum.remove(possibleNum.size() - 1);
			possibleNum.remove(possibleNum.size() - 1);
			cnt -= 2;
		}
		possibleNum.add(1);
		cnt++;
		findPossibleBinaryNum(cnt);
		possibleNum.remove(possibleNum.size() - 1);
		cnt--;
	}


}

 

두 번째: 동적 계획법을 작성해 풀어보았다. 동적 계획법이라고 하는데, 결국에는 식을 세워서 풀 수 있는 것이 제일 중요한 것 같다. 마지막에 00(0과 1을 배치하고 마지막 자릿수 두 개가 남았을 때), 또는 1(마지막 자릿수 한 개가 남았을 때)로 나눠서 풀었는데, 풀어보니 피보나치 수열을 동적 계획법으로 구현한 것과 거의 똑같았다.

package test;

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

public class test115 {
	static ArrayList<String> binaryNums;
	static ArrayList<Integer> possibleNum;
	static int N;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		binaryNums = new ArrayList<>();
		System.out.println(binaryNums.size() % 15746);
		System.out.println(findPossibleBinaryNumDp(N) % 15746);
		bw.close();
		br.close();
	}

	static int findPossibleBinaryNumDp(int N) {
		if (N == 1)
			return 1;
		if (N == 2)
			return 2;
		int[] dp = new int[N + 1];
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= N; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
		}
		return dp[N];
	}

}