[백준/C++] 1904 01타일 (S2)

유형	난이도	완료일	링크	특이사항
DP	실버2	23/02/10	https://www.acmicpc.net/problem/1904

첫 풀이(오답)

처음엔 조합을 이용해서 해결하려 했다.

1과 00을 묶어 각각 하나의 선택지라고 생각하면, AABBB를 줄세우는 확통 문제처럼 해결할 수 있게 된다.

예를 들어 N = 5라면 ”00” 은 0개, 1개, 혹은 2개까지 들어갈 수 있다.

“00”이 0개 → 1로 5칸을 꽉 채워 경우의 수가 1개(5C0),

“00”이 1개 → [ “00”, “1”, “1”, ”1”] 을 줄세우는 경우와 같으므로 4C1로 계산할 수 있다.

“00”이 2개 → [”00”, ”00”, “1”] 을 줄세우는 경우와 같으므로 3C2로 계산할 수 있다.

즉 n개의 칸을 채우는 경우 ”00”의 개수를 i라고 했을 때 경우의 수는 ( n-i C i ) 이다.

처음엔 2차원 배열에 for문으로 저 계산을 모두 해서 담아두려고 했다. 1000x1000 정도까진 가능하지만 더 커지면 무리가 온다. 게다가 N이 100만까지여서 배열 크기는 N^2로 터무니 없을 만큼 커진다.

vector로도 시도해봤지만 N이 100만에 근접하면 답이 출력되지도 않는다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr(1000001);

int main(void)
{

	int n;
	cin >> n;
	
	//int arr[n+1][n+1] = { 0, };
	//배열 대신 2차원 벡터를 사용 vector<vector<int>>
	

	for(int i = 1; i <= n; i++)
	{
		//arr[i][0] = 1;
		arr[i].emplace_back(1);
	}
	for(int i = 1; i <= n; i++)
	{
		//arr[i][1] = i;
		arr[i].emplace_back(i);
	}
		
	////////////////////////                                                                                  
		//나머지만 저장해야함
	
	for(int i = 2; i <= n; i++)
	{
		for(int j =2; j <= i; j++)
		{
			if(i==j)
				arr[i].emplace_back(1);
			else
				arr[i].emplace_back((arr[i-1][j-1] % 15746 + arr[i-1][j] % 15746) % 15746);
		}
	}
	
	///////////////////////////
	int sum = 1 ; //00이 0개인 경우의 수 1

	
	//i는 00의 개수
	for(int i = 1; i <= n/2; i++)
	{
		sum += arr[n-i][i];
	}

	
	cout << sum % 15746;
}

⇒ 메모리와 시간 모두 말도 안되게 많이 필요하다. 메모리 초과로 바로 오답 처리가 됐다.

정답 코드

#include <iostream>

using namespace std;

int arr[1000001];

//int tile(int k)
//{
//	if(arr[k]!=0)
//		return arr[k];
//	
//	else
//	{
//		arr[k] = (tile(k-1)%15746 + tile(k-2)%15746) % 15746;
//		return arr[k];		
//	}
//}

int main(void)
{
	int n;
	cin >> n;
	
	arr[1] = 1;
	arr[2] = 2;
	
	for(int i = 3; i <= n; i++)
	{
		arr[i] = (arr[i-1]%15746 + arr[i-2]%15746) % 15746;
	}
	
//cout << tile(n);
	cout << arr[n];
}

n=1일 때, 2일 때, 3일 때, 4일 때, … 를 계속 적다가 해당 정답들이 f(n) = f(n-1) + f(n-2) 구조를 이루는 것을 발견했다.

답들에 규칙성이 있을 거라고 생각해보지 않고 문제 자체에서만 규칙을 찾고 한 줄의 식으로 정리하는 방법만 고민한 것 같다.

K = (A+B) 일 때 K % C = (A%C + B%C) %C 이므로 배열을 채울 때 이 규칙을 이용해 나머지로만 채워주었다.

백만 칸의 1차원 배열을 n칸까지 채워 넣고 답을 출력했다. (재귀함수로 구현했을 때는 숫자가 10만 중반이 되자 segmentation 오류가 발생했다.)

조합을 이용해서 풀어보려고 엄청 오래 고민했는데 쉽게 풀려서 허망하기도 했지만 문제를 보는 관점을 고민해볼 수 있어서 의미있었다. 안 풀리는 한 방식으로만 붙잡고 있기보다 답일 가능성이 있는 관점이 또 뭐가 있을지 생각해보자.