1904 백준 문제풀이 (feat. 동적계획법)

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

1904번: 01타일

동적계획법 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

피보나치 수열을 보게 되면, 계속 반복되는 구조로 무수한 계산을 해야한다. 재귀함수를 통해서 코드를 간략하게 하고 반복문을 사용하지 않도록 구현을 할 수 있다. 단점으로는 메모리를 많이 차지하게 되는데, 예제를 통해 보자면

function fib(n) {
 if (n = 0)
  return 0
 else if (n = 1)
  return 1
 else
  return fib(n-1) + fib(n-2)
}

// 이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

5라는 숫자는 낮은 숫자임에도 불구하고 반복적인 작업을 엄청 해야 하는데, 수가 늘어난다면 반복적인 계산은 기하급수적으로 늘어난다. 이것을 해결하기 위해 동적계획법으로 사용하게 된다.

 

다시 문제로 돌아와서, 

출력에서 15746 나눈 나머지는 int 의 범위보다 더 큰 숫자가 발생하는 것을 방지하기 위해 쓰인 걸로 보인다.

문제의 규칙을 보게 되면, 말을 장황하게 하지만 보게되면 피보나치와 동일한 구조임을 알 수 있다.

N = 1 은 1개, N = 2일 때에는 2개, N = 3이라면 3개 이후에는 5, 8 · · · 증가를 하게 된다.

규칙을 찾기 전까지는 보이는 것만 생각을 해서 00 을 어떻게 배치를 해야 하나 했는데, 저렇게 생각하면 쉬워 보인다.

#include <stdio.h>

int dp(int number) {
	int arr[2] = { 1, 1 };
	int i = 1, c;
	while (i++ <= number)
	{
		c = arr[1] + arr[0];
		if (c >= 15746)
			c -= 15746;
		if (i & 1)
			arr[1] = c;
		else
			arr[0] = c;
	}
	return arr[number & 1];
}

int main(void) {
	int N;
	scanf_s("%d", &N);
	printf("%d", dp(N));
	return 0;
}

 처음에는 if 문으로 15746으로 뺄셈을 하지 않고 %=을 사용해서 한 줄로 표현했더니 while문 안에 있는 거라 계속 계산이 들어가게 되어 시간이 늘어났다.

 그리고 여기서는 비트연산자 &가 쓰였는데, 비트 AND이므로 두 비트가 모두 1일 때 1입니다. 하나라도 0이라면 0이 나오는 연산이기에, 비트1이 4일때, 비트 2는 1이라면 0이 된다. 비트 1이 3이고 비트 2는 1이라면 1이다.

(0100 & 0001 == 0000, 0011 & 0001 == 0001)

 코드를 뜯어보게 되면 어떻게 되어있는지 구조를 알 수 있게 된다.