https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 배열을 어떻게 만들어야 할지 고민했던 문제. dp배열을 만든 뒤로는 그냥 무난하게 풀어냈다. #include int dp[1001][3] = {0}; int min(int a, int b){ return a>b?b:a; } int index(int k){ if(k==3){return 0;} if(k==-1){return 2;} return k; } int main(){ int..

2차원 DP 를 통해 풀어줄 수 있다. www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net dp[a][b]는 완벽한 상태의 알약이 a개, 반개짜리 알약이 b개일때의 문자열의 개수이다. 완벽한 알약을 하나 복용하고 반개짜리 알약으로 만들어 줄 수 있으므로, dp[a-1][b+1]의 경우가 생길 수 있고, 반개짜리 알약이 있는 경우 ( b > 0 ) 에는 반개짜리를 먹는 경우도 추가로 더해준다. 굳이 a==0 && b==0일때 탈출하지 않는 이유는 어차피 dp[a][k]에서 a가 ..