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

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP 문제 유형 까먹을 것 같아서 오랜만에 풀어봤다. 매번 하던 재귀 방식으로 구현 했다. 우선, cache 배열을 만들어서 ret 으로 참조하도록 했고, N == 0 이 될 때까지 1, 2, 3을 뺀 케이스를 재귀로 호출과 함께 ret 에 더해주었다. 사실 나도 반복학습으로 배운 방법이라 설명이 어렵다. 전체 코드 #include #include #include using namespace std; const int MOD = 1000000..