일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
- livedata
- androidStudio
- 코루틴
- MyVoca
- architecture
- pandas
- 쿠링
- textfield
- Rxjava
- boj
- GitHub
- TEST
- Coroutine
- 암호학
- AWS
- Hilt
- activity
- Gradle
- MiTweet
- android
- 백준
- ProGuard
- 프로그래머스
- Coroutines
- Codeforces
- Kotlin
- Python
- relay
- Compose
- 코드포스
- Today
- Total
이동식 저장소
12996. Acka 본문
Acka는 악어
라고 읽는다. 모 랭커분의 닉네임이다.
12996번: Acka
첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S)
www.acmicpc.net
세 사람이 불러야 하는 곡의 개수
일단 특이 케이스부터 먼저 살펴보자.
각자 불러야 하는 개수만큼 곡을 고르는 경우의 수는
그러나 몇몇 곡을 선택하지 않는다고 해도, 최소한
따라서 적어도 하나의 곡이 선택되지 않을 때, 선택할 수 있는 곡의 범위는 일부 곡을 선택하는 경우의 수
와 그 때의 정답
을 곱한 값과 같다. 일부 곡을 선택하는 경우의 수
는 그냥 이항계수이고, 그 때의 정답
은
따라서
모듈러 연산이 있으므로 계산식에 주의하자. 이항계수를 구할 일이 많으므로 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 |