[백준 1904번 C/C++] 01타일

 

 

목차

 

 

---

 

 

[백준 1904번 C/C++] 01타일

 

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

1904번: 01타일

---

 

 

 

처음 시도한 코드 - 시간초과, 범위초과

 

#include<stdio.h>
using namespace std;

int n, cnt;

long long Combination(int m, int r)
{
	long long result=1;
	
	for (int i = 0; i < r; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    
    return result;
}


int main() {
	scanf("%d", &n);
		
	for(int i=1; i<=n/2; i++)
	{
		cnt += (Combination(n-i, i);
	}
	
	printf("%d", cnt%15);

	return 0;
}

 

조합의 합 법칙을 사용.

---

 

 

해결전략

 

이 문제의 경우, 조합의 합 법칙과 피보나치 수열은 원리가 유사하다.

 

조합을 사용하지 않고 피보나치로 구현하면 실행속도가 더 빠르게 구현할 수 있다. 

 

---

 

코드

 

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    int dp[1000001]; // dp배열
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
    }

    printf("%d\n", dp[n]);

    return 0;
}

---