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

 

 

 

 

---

 

 

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

 

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

 

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이

www.acmicpc.net

---

 

 

 

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

 

#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;
}

---