[C++] 백준 1904. 01타일

🌽 문제

왜 애를 괴롭혀

🥕 입출력

🥔 풀이

첨엔 string을 갖다가 연결 연결하면 되려나 생각했는데
시간 제한이 0.75초인 걸 보고 엄청 간단한 규칙이 있겠구만 하고 힌트를 얻었다.
쭉 적어봤더니 피보나치 수열을 따른다는 걸 알아냈다.

/*
 * arr[1] = 1; // 1
 * arr[2] = 2; // 11, 00
 * arr[3] = 3; // 111, 100, 001
 * arr[4] = 5; // 0011, 0000, 1100, 1111, 1001
 * arr[5] = 8; // 11111, 
 *              // 11100, 11001, 10011, 00111,
 *              // 10000, 00100, 00001
 * arr[6] = 13; // 111111, 
 *               // 111100, 111001, 110011, 100111, 001111,
 *               // 110000, 100100, 100001, 001001, 000011, 
 *               // 001100, 000000
 */

잔.

🥬 코드

#include <iostream>
using namespace std;

long long arr[1000001];

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

🥜 채점

첫 제출 땐 15746 mod 연산이 없어서 오버플로가 났나보다.