[백준] 1904번 : 01타일 - JAVA [자바]

www.acmicpc.net/problem/1904

1904번: 01타일

 

---

• 문제

 

 

 

 

문제의 이해 자체는 어렵지 않을 것이다.

타일은 두 종류가 있는데 1타일과 0이 두 개 이어 붙여진 00타일이 있는 것이다. 즉 1타일과 00타일을 조합할 때, 00타일은 분해할 수 없다는 의미다.

 

막상 풀어보면 그렇게 어렵지 않으니 한 번 같이 문제를 들여다보도록 하자

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이 문제는 만약 N=1 부터 경우의 수를 쭉 나열해보았다면 매우 쉽게 풀 수 있다.

 

일단 한 번 나열해보도록하자.

 

N=6까지 가능한 경우의 수들을 나열해보았다.

뭔가 규칙이 보이지 않는가??

 

보면 개수가 피보나치 수의 수열처럼 증가하고 있음을 볼 수 있다.

 

즉, N=3 일 때는 N=1 일 때와 N=2 일 때의 개수의 합인 것처럼, Tile(N) = Tile(N-1) + Tile(N-2) 을 만족한다. 이는 피보나치 점화식과 같다는 것을 알 수 있다.

 

그럼 피보나치 수에 관한 알고리즘을 그대로 적용하면 되는 거 아닌가? 만약 피보나치 수의 알고리즘에 대해 모르시는 분들이 있을 수도 있으니 다음 참고하면 좋은 포스팅을 하나 링크해두겠다.

 

st-lab.tistory.com/123

[백준] 2748번 : 피보나치 수 2 - JAVA [자바]

 

 

이제 이를 동적계획법으로 풀이하는 방법만 남았다. 위 포스팅을 보면 알겠지만, 동적계획법 말고도 반복문을 통해 풀어낼수도 있다. 그러나 문제 취지상 일단 동적계획법으로 풀이를 해보고자 한다.

 

동적계획법은 이미 연산을 했던 결과가 있으면 해당 값을 이용하여 중복되는 연산을 줄여 성능을 조금이나마 개선하는 방법인 메모이제이션을 활용하는 방법이다. (이에대한 내용은 위 참고링크에서 자세하게 설명하고 있다.)

 

즉, 피보나치 수 2 글에서도 보면 알겠지만, Fibonacci(4)를 구한다고 가정하면 Fibonacci(2)를 두 번 계산하게 되는데, 이 때 이를 한 번만 계산하도록 하는 방법이다. 이를 코드로 풀어내면 다음과 같다. (참고로 피보나치 수와는 다르게 2번째 배열은 2이므로 2일 경우는 2로 초기화 해주어야 한다.)

static int[] dp = new int[size];	// 배열 비어있는 표시는 -1 이라고 가정
 
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
 
int Tile(int N) {
	if(dp[N] == -1) {	// 해당 배열에 값이 없을경우 재귀호출
		dp[N] = Tile(N - 1) + Tile(N - 2);
 	}
	return dp[N];
}

 

물론 int[] 배열은 디폴트값이 0으로 되어있으므로 0이 입력될 때는 비어있는 게 아니기 때문에 모든 배열을 -1 같은 나올 수 없는 수로 초기화 해줄 필요가 있다. (특히 이 번 문제에서는 나머지 값을 저장해야 하므로 나머지 값이 0일 수도 있기 때문에 초기화는 더더욱이 필요하다)

 

[주의]

참고로 Integer 배열로 풀이하는 방법도 있으나 입력 값이 1,000,000이라 잘못하면 메모리 부족으로 stackoverflow 에러를 내뱉을 수 있다. 필자가 테스트 해보니 역시나 Integer 래퍼 클래스 배열의 경우는 런타임 에러라는 결과를 받았다.

 

이유는 Integer의 경우 참조 유형으로 객체 타입이기 때문에 16byte 의 크기를 갖는다.

이렇기 때문에 메모리 할당시 heap영역에서 주소 영역으로 갈 수 있다보니 stack영역에 메모리가 거의 꽉차게 되면 heap영역과 충돌할 수 있어 위와같은 stackoverflow을 뱉어낸다. int 형은 4바이트인 것에 비해 Integer로 쓰면 16바이트로 메모리 오버헤드가 300%나 된다. 그렇기 때문에 int형 배열로 풀 수 밖에 없다. 

 

아마 대부분의 컴퓨터에서는 큰 수를 입력할 경우 stackoverflow를 뱉어낼 것이다.

 

 

그리고 우리는 경우의 수를 15746 으로 나눈 값, 즉 dp[N] % 15746 을 출력해야한다.

아마 이 부분을 제대로 확인하지 않고 제출하는 경우 때문에 정답비율이 낮지 않은가 싶다. 여튼, 이를 적용하면 동적계획법을 이용한 방법의 전체적인 구조는 다음과 같이 된다.

 

static int[] dp = new int[size];	// 배열 비어있는 표시는 -1 이라고 가정
 
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
 
int Tile(int N) {
	if(dp[N] == -1) {	// 해당 배열에 값이 없을경우 재귀호출
		dp[N] = (Tile(N - 1) + Tile(N - 2)) % 15746;
 	}
	return dp[N];
}

 

여기서 이러한 질문을 던지는 분들이 계실 것이다. 각 배열에 나머지값을 저장하면 다른 재귀에서 해당 값을 쓰게되면 나머지 값을 쓰게되는데 그러면 원래 값의 나머지와 달라지지 않나요?

 

이 부분은 모듈러 연산의 분배법칙을 이해하면 쉽다. 설명하긴 길기 때문에 (A+B)%C = (A%C + B%C)%C 가 성립한다는 것만 알아두자.

 

물론 이 방법이 효율적인 것은 아니다. 위 방법의 경우 아무리 중복 연산을 제외하고 시간복잡도는 이론적으로 O(N)이라 하지만 매 재귀마다  조건문을 검사하는 등 오버헤드가 커질 수밖에 없을 것이다. 그래서 반복문으로 푸는 것이 더욱 효율적이긴 하다.

 

반복문으로 풀이하는 방법은 따로 설명하지 않고 아래 풀이의 마지막에서 보여주도록 하겠다. (재귀의 반환 경로를 그대로 풀어서 반복문으로 만들면 되기에..)

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

이전의 피보나치 수 2와 거의 동일한 방법이기 때문에 크게 설명할 부분은 없었다. 이번에는 입력을 Scanner 와 BufferedReader 을 각각 사용해보면서 성능차이를 확인해보고 마지막에는 반복문을 통한 풀이 방법을 보여주고자 한다.

다음 3가지 방법으로 풀이해볼 것이다.

 

1 . 재귀 + Scanner

2. 재귀 + BufferedReader

3. 반복문 + BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [재귀 + Scanner]

 

import java.util.Scanner;

public class Main {

	public static int[] dp = new int[1000001];;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;

		// -1 로 초기화
		for(int i = 3; i < dp.length; i++) {
			dp[i] = -1;
		}
		
		System.out.println(Tile(N));
		
	}
	
	public static int Tile(int N) {
		
		if(dp[N] == -1) {
			dp[N] = (Tile(N - 1) + Tile((N - 2))) % 15746;
		}
		return dp[N];
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

 

 

 

---

- 방법 2 : [재귀 + BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

 

 

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

public class Main {

	public static int[] dp = new int[1000001];;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;

		// -1 로 초기화
		for(int i = 3; i < dp.length; i++) {
			dp[i] = -1;
		}
		
		System.out.println(Tile(N));
		
	}
	
	public static int Tile(int N) {
		
		if(dp[N] == -1) {
			dp[N] = (Tile(N - 1) + Tile((N - 2))) % 15746;
		}
		return dp[N];
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 설명할 것도 크게 없다..

 

---

- 방법 3 : [반복문 + BufferedReader]

 

 

 

동적 계획법을 변형하여 단순 반복문으로 풀이하는 방법이다. 필자가 이전에 잠깐 언급한적이 있었는데, 대부분의 재귀 문제는 반복문으로 풀 수 있다고 한 적이 있다. 적어도 필자는 아직까지 재귀를 반복문으로 변형하지 못하는 케이스를 본 적은 없다.

 

방법은 매우 간단하다. 먼저 N=1 일 때와 N=2 일 때의 초기 값을 변수로 두고, N 이 2보다 큰 값일 경우 반복문을 통해 두 변수를 합해주는 방식으로 하면 된다. (여기서도 메모이제이션을 쓸 필요가 없다.. 아쉽다..)

 

말로 하면 어려울테니 코드로 보자.

 

 

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

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());

		System.out.println(Tile(N));

	}

	public static int Tile(int a) {

		if (a == 1) {
			return 1;
		} 

		if (a == 2) {
			return 2;
		}

		// 초기 값 
		int val1 = 1;
		int val2 = 2;
		int sum = 0;

		for (int i = 2; i < a; i++) {
			sum = (val2 + val1) % 15746;	// 이전 값과 이전의 이전 값의 합 
			val1 = val2;	// 이전의 이전 값은 이전 값으로 변경 
			val2 = sum;		// 이전 값은 현재 합 값으로 변경 
		}

		return sum;

	}

}

 

 

이렇게 간단하게 풀어낼 수도 있다. 이 코드가 사실 이전 재귀에 비해 훨씬 효율적이긴 할 것이다. (물론 상황에 따라 다르기 때문에 그렇다고 Top-Down(재귀)방식을 몰라도 된다는 것은 아니다.)

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 21194429  -  방법 3 : 반복문 + BufferedReader

채점 번호 : 21194421  -  방법 2 : 재귀 + BufferedReader

채점 번호 : 21194412  -  방법 1 : 재귀 + Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다. 또한 반복문으로 풀어낸 방법이 메모리나 시간측면에서도 훨씬 빠르다는 것을 볼 수 있다.

---

• 정리

 

이 번 문제는 Top-Down(재귀) 한계를 볼 수 있었다. 어느 방법이 되었든 재귀 자체가 오버헤드가 커서 메모리 측면, 시간 측면에서는 효율적이지 않은 것은 사실이다.

 

그럼에도 Top-Down방식을 알아야 하는 이유는 점화식으로 표현하는 것을 그대로 재귀형태로 옮겨놓은 것이기 때문에 누가 코드를 보더라도 이해하기 쉽고 코드를 작성하는데 시간도(즉, 개발시간도) 현저하게 줄어든다.

 

만약 어려운 점이 있다거나 이해가 안되는 부분이 있다면 댓글 남겨주신다면 최대한 빠른 시일 내에 답변드리도록 하겠다. 동적계획법이 아이디어는 쉽더라도 막상 구현하려고 하면 어려운 단계이기도 하기 때문에 확실히 알고 갈 수 있도록 최대한 도움을 드리겠다.