[백준] 2666번: 벽장문의 이동

https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 완전탐색과 재귀를 이용한 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 22 // dp[i][j][k] = i번째 문을 열어야 할 때, 현재 j와 k번째 문이 열려있다. int dp[MAXN][MAXN]MAXN]; 이번에 열어야 하는 문과 가까운 문을 연다고 해서 반드시 최적이 보장되지는 않는다. 즉, greedy하지 않다. 따라서 왼쪽과 오른쪽을 모두 변화시키면서,..

[백준] 1106번: 호텔

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net DP 중에 전형적인 배낭 문제다. DP 배열을 아래처럼 정의한다. #define MAXC 100001// 1000명 X 100원 = 100000원 int dp[MAXC];// dp[i]: i원을 사용했을 때, 늘어난 최대 사람 수 사용한 금액을 기준으로 dp 배열을 만든다. 최대 사용 가능 금액은, 최악의 경우 최대 1,000명에 1인당 최대 100원이 든다고 생각했을 때 100,000원 이라..