[백준 / BOJ] 1904번: 01타일

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

1904번: 01타일

 

 

---

 

코드

---

#include <cstdio>

int r[1000001] = { 0, 1, 2, };

int main() {
	int n; //1 ≤ N ≤ 1,000,000
	scanf("%d", &n);
	for (int i = 3; i <= n; i++) {
		r[i] = (r[i - 1] + r[i - 2]) % 15746;
	}
	printf("%d", r[n]);
	return 0;
}

 

 

 

---

 

 

처음엔 재귀로 풀려고 했는데, long long 범위를 넘어갈 만큼 큰 값이 나오는 경우도 있어 15746으로 나눈 나머지를 저장해 주어야 한다. 피보나치 수열과 비슷한 규칙을 찾아내는데에 시간이 오래걸리지 않았다. 왠지 그냥 감....? 운이 좋았던건지 쉬운 문제인건지 모르겠다. 규칙이 찾기 힘든 문제도 풀 수 있어야하는데 많이 풀다보면 늘겠지 하하..

+ 처음에 재귀함수를 사용해서 풀려고 했는데 오버플로우가 생겨서 반복문으로 풀게 됐다. 졸려서그런건지 아무리봐도 같은코드같은데 왜 오버플로우가 생겼는지 이해가 안되는중... 내일 다시보기!!

#include <cstdio>

long long r[1000001];

long long f(int n) {
	if (n == 1) return 1L;
	if (n == 2) return 2L;
	if (r[n] == 0) r[n] = (f(n - 1) + f(n - 2)) % 15746L;
	return r[n];
}

int main() {
	int n; //1 ≤ N ≤ 1,000,000
	scanf("%d", &n);
	printf("%lld", f(n));
	return 0;
}