티스토리 뷰
https://www.acmicpc.net/problem/4811
4811번: 알약
입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.
www.acmicpc.net
간단한 dp 문제였습니다.
알약 하나가 반개로 쪼개져서 조금 햇갈릴 수 있지만, 케이스만 잘 나누면 쉽습니다.
dp[w][h] 를 W가 w개, H가 h개 남았을 때라고 하면,
1. H밖에 안 남은 경우, 즉 항상 dp[0][h] = 1 입니다. H밖에 안 남았으니 ...HHHH..HHH 와 같은 경우 밖에 없습니다.
2. W밖에 안 남은 경우
W만 남은 경우, W 중 1개를 먹으면 W는 w-1개, H 1개가 됩니다. 그러므로 dp[w][0] = dp[w-1][1] 입니다.
3. 나머지 경우
W가 w개, H가 h개 남은 경우, W가 나왔다고 치면, 반 쪽을 먹고 반 쪽이 새로 생깁니다. (dp[w-1][h+1])
그리고 H가 나온 경우, W는 w개, H는 h-1개 남았으므로 dp[w][h-1]개의 경우가 있습니다. 이 두 경우가 모두 나올 수 있으므로
dp[w][h] = dp[w-1][h+1] + dp[w][h-1] 입니다.
코드는 다음과 같습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1701 Cubeditor C++ (0) | 2021.11.23 |
|---|---|
| 백준 14466 소가 길을 건너간 이유6 c++ (0) | 2021.11.18 |
| 백준 14226 이모티콘 C++ (0) | 2021.11.04 |
| 백준 16936 나3곱2 python3 (0) | 2021.09.21 |
| 백준 C++ 1525 퍼즐 (0) | 2021.09.20 |
댓글