[백준][JAVA알고리즘]1904번 풀이(01타일) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1904번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1904 (01타일)

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

 

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰인 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 00 타일을 두 개 붙인 한 쌍의 0000 타일들만이 남게 되었다.

 

그러므로 지원이는 타일로 더 이상 크기가 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으로 나눈 나머지를 출력한다.

제한

시간제한 : 0.75 초 (추가 시간 없음)

입력 예시

4

출력 예시

5

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static int[] tile;
	static int N ;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		tile = new int[N+1];
		
		System.out.println(tile_f(N));
		
}
	public static int tile_f(int fibo) {
		if(tile[fibo]!=0)
		return tile[fibo];
		
		if(fibo == 1)
			return 1;
		else if(fibo == 2)
			return 2;
		else if(fibo > 2)
			return tile[fibo] = (tile_f(fibo-1) + tile_f(fibo-2))%15746;
		else
			return fibo;
	}

}

해당 01타일 알고리즘은 2가지를 알아야 쉽게 풀이할 수 있습니다. 첫 번째는 바로 01 타일의 패턴! 두 번째는 메모이제이션 기법입니다.

 

여러 번 말했듯이 동적 계획법 문제에서 메모이제이션기법은 거의 무조건 사용해 주어야 합니다. 혹시 메모이제이션 기법이 뭔지 모르시겠다면, 아래에 있는 해당 알고리즘을 간략히 보고 오시면 됩니다.

보기 귀찮으시다 하시는 분은 STEP1에 있는 메모이제이션이란만 보셔도 무방합니다!

[백준][JAVA알고리즘]9184번 풀이(신나는 함수 실행) - 초보도 이해하는 풀이

 

그럼 이제 2가지를 STEP을 따라 이해해보도록 하죠

---

알고리즘 흐름도

 입력받기 -> 메모이제이션 체크해주기 -> 아니라면 피보나치수열 적용하기 -> 결과 출력하기

---

STEP1 01타일 패턴 찾기

 간단히 생각해보죠 만약에 n이 7이라면 어떠한 경우의 수들이 있을까요?

N = 1
만들 수 있는 경우의 수 1개
1

N = 2
만들 수 있는 경우의 수 2개
11 / 00

N = 3
만들 수 있는 경우의 수 3개
111 / 100 / 001

N = 4
만들 수 있는 경우의 수 5개
1111 / 1100 / 0011 / 0000 / 1001

N = 5
만들 수 있는 경우의 수 8개
11111 / 10000 / 00100 / 00001 / 11100 / 11001 / 00111 / 10011

N = 6
만들 수 있는 경우의 수 13개
111111 / 111100 / 111001 / 110011 / 100111 / 001111 / 110000 / 100100 / 100001 
/001100 / 001001 / 000011 / 000000

개수가 1 2 3 5 8 13 이렇게 늘어나는 것을 알 수 있죠. 네 바로 피보나치수열입니다. N이 1일 때와 2일 때만 지정해 준 뒤 뒤에 타일의 개수는 피보나치로 풀면 끝!

---

STEP2 메모이제이션 구현해주기

 그러나 해당 알고리즘은 동적 계획법으로 풀어야 합니다. 그렇기 위해서는 해당 값을 저장할 배열이 따로 필요합니다. 해당 배열을 tile이라고 지정하고 보여드리겠습니다.

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		tile = new int[N+1];
		
		System.out.println(tile_f(N));
}

이렇게 tile을 지정해 줍니다. tile의 크기를 N+1로 지정한 이유는 저희가 헷갈리지 않도록 하기 위해서입니다. 인덱스랑 타일 개수랑 일치시켜주기 위해서이죠. 뭐 타일이 0개이면, 0을 넣어줘도 큰 상관이 없기 때문이죠.

 

이제 이를 이용해서 STEP 3로 이동해보죠

---

STEP 3 이외의 피보나치수열 적용하기

public static int tile_f(int fibo) {
		if(tile[fibo]!=0)
		return tile[fibo];
		
		if(fibo == 1)
			return 1;
		else if(fibo == 2)
			return 2;
		else if(fibo > 2)
			return tile[fibo] = (tile_f(fibo-1) + tile_f(fibo-2))%15746;
		else
			return fibo;
	}

 아주아주 간단합니다. 가장 먼저 고려해 줘야 하는 IF문은 바로 메모이제이션에 값이 있는가!

 

tile [fibo]의 값이 0이 아니라면, 값이 저장되어있다는 의미가 되죠. 그렇게 되면 재귀나 반복문을 더 이상 안 돌려도 되니 바로 해당 값은 반환해 주면 됩니다.

 

그리고 일반 피보나치수열처럼 fibo가 1일 때, 2일 때는 각 1과 2를 반환해 주도록 하죠.

 

마지막 else if는 일반 피보나치수열처럼 해당 tile [] 메모이제이션배열에 그 이전 값과 이이전 값을 더해서 넣어주면 끝! 뒤에 %15746 값은 문제에서 나누어 주도록 하라고 하였으니 넣어준 값입니다~

 

(마지막 else는 음수 값이 나오면 해당 값은 반환해 오류임을 알려주려고 작성하였습니다.)

 

이제 슬슬 동적 계획법도 풀이 방법이 잡혀가고 있음을 알 수 있습니다.