BOJ 14849

 

 

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

 

코드

http://boj.kr/bbf8635a8ab74ad7bfe625ff7021af42

 

난이도 : P2

 

Elapse Time : 90min

 

이 문제를 보고 $T=100$, $q=100$, $v=10^5$인 것이 먼저 눈이 들어왔다. $O(Tqv)$의 코드는 시간에 안 들어올 것이기 때문에 $c_1$, $c_2$, $c_3$, $c_4$를 입력받고 쿼리를 입력받기 전에 무언가를 미리 계산을 해놔야겠다는 생각을 했다. 동전을 무제한으로 사용 가능할 때 $x$를 만드는 경우의 수를 구해놓으면 쿼리 처리를 할 수 있을지 생각해 보았다. 쿼리에서는 동전 개수에 제한이 있는데 포함과 배제로 제한보다 많이 사용하는 경우를 빼주는 것은 동전 종류가 4가지밖에 안되기 때문에 빠르게 할 수 있기 때문에 가능하다. 동전을 무제한으로 사용 가능할 때 합으로 특정 값을 만드는 경우의 수를 구하는 것에서 FFT가 먼저 생각났다. $0\leq x\leq 10^5$인 $x$중 $v_i$에는 $c_i$의 배수들에 1을 넣고 나머지에는 0을 넣어 FFT를 해주면 특정 값을 만드는 경우의 수를 구할 수 있다. 시간복잡도도 $O(Tvlogv)$이기 때문에 아슬아슬하게 될 것 같았다. 하지만 FFT의 결과가 잘 나오지 않아 50분을 썼다. 실수 오차 때문인가 싶어 NTT로 바꿔서 계산했더니 맞는 값이 나왔다. 이후 쿼리를 처리하는 부분을 포함과 배제를 활용하여 짜주었더니 시간초과가 나왔다. NTT가 느리기 때문인 것 같아 NTT 말고 다른 방법을 찾아보았다. 다른 방법으로는 $dp$가 가능해 보였다. $dp$를 짤 때도 포함과 배제를 활용하여 $dp[x]=dp[x-c_i]-dp[x-c_i-c_j]+dp[x-c_i-c_j-c_k]-dp[x-c_1-c_2-c_3-c_4]$식을 세워 구하였다.