[백준] 11726(2XN 타일링) C++

처음엔 DP 방식이아닌 조합(combination)을 이용한 공식을 사용하여 풀려고 시도했다

n이 1000인 경우 1000C0 + 999C1 + ... + 501C499 + 500C500 이런 식이 나오는데 당연히 시간초과가 나와버렸다

combination의 시간을 줄이는 알고리즘을 찾아보고 생각해봤지만 해결할 수가 없어서 DP 방식을 다시 생각해 봤다

다른 사람의 코드를보니 P(n) = P(n-1) + P(n-2)란 점화식이 나왔더라..이 간단한게 왜 안 보였는지...

 

그리고 문제에선 해당 경우의 수를 10,007로 나눈 나머지를 출력하란다

당연히 n에 대한 경우의 수를 구한다음에 10,007로 나눈 나머지를 출력했는데

범위를 초과해버린다 아마 unsigned long long 을 써도 초과하는 듯 한다.

 

여기서 알게 된건 나머지를 구하는 것도 곱셈과 마찬가지로 분배 법칙이 적용된다는 것이다.

 

이 문제를 풀며 기록하고 싶은 내용은

1. nCr 알고리즘의 높은 시간 복잡도는 해결할 수 없음

(적어도 문제를 푸는 중에는..따라서 nCr을 사용하는게 옳지 않은 방향일 가능성이 높음)

2. 나머지 구하는 것도 분배법치기 적용된다.

(변수 범위 때문에 골치 아플 때 떠올려보자)

 

https://hongku.tistory.com/162

백준/11726번 :: 2xn 타일링 (C/C++ 구현)