https://www.acmicpc.net/problem/22348
22348번: 헬기 착륙장
각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다.
www.acmicpc.net
테스트 케이스가 1만개라고 주어졌기에, 전처리를 잘 해서 쿼리에서 소요되는 시간을 줄여야 한다.
문제에서 관찰해야 하는 사실은 헬기 착륙장을 만들었을 때 빨강 페인트와 파랑 페인트의 통 수의 합이 447가지 경우밖에 없다는 것이다. 1, 1+2, 1+2+3,...1+2+...+447. 448까지의 합이 100128이므로 이 이후는 따질 필요가 없겠다.
결국 각각 447가지 경우에 대해서 빨강 페인트의 통 수가 50000가지가 가능하므로 [447][50000]배열을 만들어 DP 해주면 각 경우의 수를 구할 수 있다. 쿼리에서는 447개 경우에 대해 가능한 빨강 페인트 통 개수의 값들을 다 더해 주면 되는데, 이건 구간 합이므로 Prefix sum으로 해결하면 447번의 연산으로 하나의 쿼리를 처리하므로 대충 O(N√N + Q√N)정도의 시간 복잡도로 해결했다고 보면 되겠다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 3090 차이를 최소로 (0) | 2023.01.05 |
|---|---|
| 백준 7469 K번째 수 (0) | 2023.01.05 |
| 백준 15972 물탱크 (0) | 2023.01.05 |
| 백준 1315 RPG (0) | 2023.01.05 |
| 백준 1178 간선 추가 (1) | 2023.01.05 |
