백준 4811번: 알약 (C++)

https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 풀이 문자열로 표현되어 있지만 사실 경우의 수 문제이다. 최대 1000개의 테스트케이스가 있기 때문에 매번 계산을 하게 되면 시간초과가 나온다. 이전에 계산했던 결과를 저장해야 시간초과가 나지 않아서 DP로 접근했다. cache 배열은 한 조각의 알약의 개수와 반 조각 개수의 최댓값 만큼의 크기로 선언했다. 즉, idx = 한 조각, cnt = 반 조각의 알약 개수다. (앞으로 문제에 맞게 변수 명을 설정하자.)..

2023.03.05