개요

[링크]백준 1904번: 01타일

• 입력
  첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

• 출력
  첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

접근 방식

• 처음엔 [백준 2193] 과 같은 방식으로 함수에 0이 들어왔었는지,
  1이 들어왔었는지 조사를 하는 방식으로 구현하려 했다.
  하지만 0이 들어왔을 땐 두개를 건너 뛰어서 까다로웠다.

• 두 번째 방식은
  점화식을 세우는 방법이다.
  n번째 타일의 경우의 수를 F(n)이라 했을 때
  n번째 타일이 1이 들어왔을 때 경우의 수는 F(n-1),
  n번째 타일이 0이 들어왔을 때 경우의 수는 F(n-2)이다.
  따라서 F(n)=F(n-1)+F(n-2) 이고 이 식은 피보나치 수열이다.
  15749로 나눈 나머지를 계산해야하므로
  A+B를 C로 나눈 나머지는 (A%C+B%C)%C를 이용한다.

코드

#include<iostream>
#include<memory.h>

using namespace std;
const int MAX = 1'000'001;
const int devideBy = 15746;
long long dp[MAX];
void input(int& amount) {
	cin >> amount;

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
}

void solution(int amount) {	
	
	for (int i = 3; i <= amount; i++) {
		dp[i] = (dp[i - 1]%devideBy + dp[i - 2]%devideBy)%devideBy;
	}
	cout << dp[amount];
}


int main() {
	
	int amount = 0;
	input(amount);
	solution(amount);
}	

문풀후생

처음엔 탑다운 방식으로 구현했었는 데,
이미 구한 값이면 return을 해주는 식으로 중복 값을 계산 안하게 짰다.
하지만, 1만 언저리만 가도 답이안나오고 프로그램이 종료되어서
찾아보니 너무 깊은 재귀에 각 재귀마다 변수들이 선언되서 스택이 터질 수 있다는
글들을 보았다.
너무 큰 범위의 배열에선 바텀업을 쓰는게 더 빠르고 안전한 것 같다.