알약

[백준 4811] 알약 C++

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 dp[한 조각 알약의 개수][반 조각 알약의 개수]를 통해서 메모이제이션을 해주면 쉽게 풀린다. 한 조각 알약이 0개라면 앞으로 반 조각을 먹는 경우밖에 없으므로 return 1을 하는 기저 조건이 된다. 재귀 함수 내부에서는 한 조각 알약의 개수가 0보다 크면 한 조각을 빼고 반 조각을 추가해서 재귀 호출을 하고 마찬가지로 반 조각 알약의 개수가 0보다 크면 반 조각만 빼고 재귀호출을 하는 식으로 구현을 했다. 2. 코드 top d..