[JAVA] BOJ(백준) - 01타일 - 1904

문제내용

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

1904번: 01타일

 

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 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으로 나눈 나머지를 출력한다.

 

---

문제 접근 방법

타일의 길이 N에따라 타일 개수를 15746으로 나눈 나머지 값을 출력하라는 말을 보고 규칙을 찾아보기 위해 N=1, 2, 3, 4, 5, 6 까지 타일개수를 세어봐야겠다 생각했고 실제로 세는데 얼마 걸리지 않았다.

 

딱 봤을때 얼마 안걸릴꺼 같으면 그냥 직접 세보면서 규칙 찾는게 좋을것 같다.

 

여튼 세어본 결과 길이 N이 주어졌을때 타일의 개수는

 

N	타일 개수( f )
1	1
2	2
3	3
4	5
5	8
6	13

위의 표처럼 나타낼수 있고

이 표를 통해 타일 개수 f 를 식으로 f(n) = f(n-1) + f(n-2)  이렇게 표현할 수 있다.

 

그럼 풀이에서 필요한건

타일의 개수%15746 의 값을 저장해줄 DP배열

하나만 있으면 풀수 있다.

 

 

풀이는 두가지 이고

나는 재귀를 통해 풀었지만(top - down)

효율이 훨씬 좋은 풀이법은 for문을 이용해 푸는 방법이다(bottom-up)

 

풀이를 보자.

 

---

풀이

재귀 풀이

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

/**
 * 01 타일
 * 백준 - DP
 * f(n) = f(n-1) + f(n-2)
 * @author USER
 *
 */
public class Main {
	static Integer[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		dp = new Integer[1000001]; //N의 최대 길이만큼 크기로 설정
		int N = Integer.parseInt(br.readLine());
		
		dp[0] = 0; //N=0 일때, 타일개수%15746 = 0
		dp[1] = 1; //N=1 일때, 타일개수%15746 = 1
		dp[2] = 2; //N=2 일때, 타일개수%15746 = 2
		dp[3] = 3; //N=3 일때, 타일개수%15746 = 3
		
		zoTile(N); //N일때 타일개수%15746 구하는 함수.
		
		System.out.println(dp[N]);
	}
	
	public static int zoTile(int n) {
		if(dp[n]!=null) {//저장된 값이 있다면 dp[n] 반환
			return dp[n];
		}
		//저장(계산)한 값이 없을땐 재귀로 계산 후 dp배열에 저장하고 dp[n]반환
		return dp[n] = (zoTile(n-1) + zoTile(n-2))%15746;
	}
}

 

---

for문 풀이

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

/**
 * 01 타일
 * 백준 - DP - bottomUp
 * f(n) = f(n-1) + f(n-2)
 * @author USER
 *
 */
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 f = 0; //f(n)
		int f1 = 1; //f(n-1)
		int f2 = 0; //f(n-2)
		
		
		//0부터 입력받은 N값까지 맨 아래(첫번째)부터 하나씩 마지막까지 계산함.
		for(int i=0; i<N; i++) {
			f = (f2+f1)%15746; 
			f2 = f1;
			f1 = f;
		}
		
		System.out.println(f);
	}
}

 

---

마치며

규칙만 찾아내면 되는 문제인데 규칙 찾는게 어렵게 돼있다면 어려운 문제 였겠지만 쉽게 찾을수 있어서 난이도는 높아보이지 않는다!