이동식 저장소

12996. Acka 본문

Problem Solving/BOJ

12996. Acka

해스끼 2023. 4. 14. 17:57

Acka는 악어라고 읽는다. 모 랭커분의 닉네임이다.

 

12996번: Acka

첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S)

www.acmicpc.net


세 사람이 불러야 하는 곡의 개수 a, b, c가 주어질 때, 만들 수 있는 앨범의 개수를 구해 보자. 뭔가 고등학교 확통 느낌이 나는 문제이다.

 

일단 특이 케이스부터 먼저 살펴보자. a+b+c<s라면 앨범을 만들 수 없다. 또, a+b+c=s라면 그냥 중복순열을 계산하면 된다. 이제 일반적인 경우를 생각해 보자. 구하는 정답을 solve(s)라고 하겠다.

 

각자 불러야 하는 개수만큼 곡을 고르는 경우의 수는 (sa)×(sb)×(sc)이다. 그런데 이렇게 하면 선택되지 않는 곡이 있을 수 있으므로, 적어도 하나의 곡이 선택되지 않는 경우를 빼면 된다.

 

그러나 몇몇 곡을 선택하지 않는다고 해도, 최소한 max개는 선택해야 한다. 곡 개수가 더 적어지면 한 사람이 같은 곡을 두 번 선택해야 하는 상황이 되기 때문이다.

 

따라서 적어도 하나의 곡이 선택되지 않을 때, 선택할 수 있는 곡의 범위는 [max(a, b, c), s)이다. 이제 곡의 일부만을 골랐을 때 앨범의 개수를 계산하면 된다. 이 값은 일부 곡을 선택하는 경우의 수그 때의 정답을 곱한 값과 같다. 일부 곡을 선택하는 경우의 수는 그냥 이항계수이고, 그 때의 정답solve의 재귀로 구할 수 있다.

 

따라서  i[max(a, b, c), s)에 대해 (si)×solve(i)를 구하고, 각각의 값을 정답에서 빼면 된다.

 

모듈러 연산이 있으므로 계산식에 주의하자. 이항계수를 구할 일이 많으므로 dp로 미리 계산해 두면 좋다.


생각보다 시간을 많이 썼다. 이 정도는 1시간 안에 풀어야 하는데..

'Problem Solving > BOJ' 카테고리의 다른 글

14922. 부분평균  (0) 2023.05.02
27979. 볼링장 아르바이트  (0) 2023.04.29
1572. 중앙값  (0) 2023.04.10
1615. 교차개수세기  (0) 2023.03.30
14719. 빗물  (1) 2023.03.25
Comments