dp[L][R][dir]을 "구간 [L,R]에 모든 번호의 램프가 꺼질 때까지의 (구간 내에 포함되지 않은 램프를 포함한 모든 램프의) 에너지 소비량의 최솟값"으로 정의하자. (단, [L,R]이 V를 포함할 때에만 정의된다.) dir은 모든 램프를 끈 뒤 가로등 L에 위치하는지 R에 위치하는지를 나타내는 변수이다. ([L,R]의 모든 램프를 에너지 소비를 최소화하며 끄는 것을 마치면 항상 L 또는 R에서 작업을 마무리함을 관찰하자.)
이 때, dp[L][R][0]은 dp[L+1][R][0]에서 (L+1번 램프의 위치에서 L번 램프까지 이동하는 동안 소비된 에너지의 양), 즉 (L+1번 램프와 L번 램프 사이 거리) * ([L+1,R]에 포함되지 않는 램프의 개수)을 더한 값과 dp[L+1][R][1]에서 (R번 램프의 위치에서 L번 램프까지 이동하는 동안 소비된 에너지의 양), 즉 (R번 램프와 L번 램프 사이 거리) * ([L+1,R]에 포함되지 않는 램프의 개수)를 더한 값 둘 중 작은 값이 된다. 이와 같은 방식으로 dp[L][R][1]에 대한 식 또한 얻을 수 있다.
각 [L,R] 구간에 대한 계산은 해당 구간이 포함하는 더 작은 크기의 구간에 대한 값만을 이용해 계산하므로 위와 같은 점화관계를 통해 문제를 충분히 해결할 수 있음을 관찰할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
typedef long long ll;
int N, V;
ll dp[1001][1001][2];
ll dist[1001], watt[1001];
ll psum[1001];
ll func(int L, int R, int dir) {
if (dp[L][R][dir]) return dp[L][R][dir];
ll& ret = dp[L][R][dir] = 1000000007;
if (dir == 1 && R > V) {
ret = min(ret, func(L, R - 1, 0) + (dist[R] - dist[L]) * (psum[L - 1] + psum[N] - psum[R - 1]));
ret = min(ret, func(L, R - 1, 1) + (dist[R] - dist[R - 1]) * (psum[L - 1] + psum[N] - psum[R - 1]));
}
else if (dir == 0 && L < V) {
ret = min(ret, func(L + 1, R, 0) + (dist[L + 1] - dist[L]) * (psum[L] + psum[N] - psum[R]));
ret = min(ret, func(L + 1, R, 1) + (dist[R] - dist[L]) * (psum[L] + psum[N] - psum[R]));
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> V;
for (int i = 1; i <= N; i++) {
cin >> dist[i] >> watt[i];
psum[i] = psum[i - 1] + watt[i];
}
dp[V][V][0] = dp[V][V][1] = 1;
cout << min(func(1, N, 0), func(1, N, 1)) - 1;
}
두 인접한 사람들의 키의 차들의 총합이 가장 작아지게끔 Mirko의 가족 K명의 사이사이(맨 앞과 맨 뒤 포함)에 다른 N-K명을 적절히 집어넣는 문제이다.
Mirko의 가족의 키의 최댓값을 kmx, 최솟값을 kmn이라 하자. 이 때 Mirko의 가족이 아니고 키가 kmn과 kmx 사이인 사람은 인접한 두 가족의 키 사이에 들어가는 구간에 (순서에 맞춰) 들어가는 식으로 줄을 서야 함을 쉽게 관찰할 수 있다.
이 문제를 어렵게 하는 것은 Mirko의 가족이 아닌 사람 중 키가 kmx보다 크거나 kmn보다 작은 사람들을 넣는 과정이다. 단순하게 생각하면 키가 kmx인 Mirko의 가족 주변에 키가 kmx보다 큰 사람들을 적절한 순서로 넣고 키가 kmn인 Mirko의 가족 주변에 키가 kmn보다 작은 사람들을 적절한 순서로 넣으면 문제를 해결할 수 있어보인다. 하지만 이러한 방식의 배치로는 다음과 같은 케이스를 통과하지 못한다.
Mirko의 가족들: [1500, 1600, 1400, 1500] 추가로 들어갈 사람들: 1000, 2000
이와 같은 케이스에서는 키가 2000인 사람이 키가 1600인 사람의 주변에 들어가는 것 보다는 줄의 한쪽 끝에 서는 것이 이득임을 관찰할 수 있다. 키가 1000인 사람이 키가 1500인 사람의 주변에 들어가는 것 보다는 줄의 다른 한쪽 끝에 서는 것이 이득임 또한 관찰할 수 있다.
이와 같은 관찰을 포함하면, 키가 kmx보다 큰 사람들 또는 kmn보다 작은 사람들이 줄을 서야하는 위치의 경우들을 아래와 같이 7가지로 분류할 수 있다.
1) 키가 kmx보다 큰 사람들은 맨 왼쪽에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에
2) 키가 kmx보다 큰 사람들은 맨 왼쪽에, kmn보다 작은 사람들은 맨 오른쪽에
3) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 맨 왼쪽에
3) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 맨 오른쪽에
5) 키가 kmx보다 큰 사람들은 맨 오른쪽에, kmn보다 작은 사람들은 맨 왼쪽에
6) 키가 kmx보다 큰 사람들은 맨 오른쪽에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에
7) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에
키가 kmx보다 큰 사람과 키가 kmn보다 작은 사람 모두를 왼쪽에 또는 모두를 오른쪽에 몰아넣을 경우는 존재하지 않음을 확인하자.
위의 각 경우별로 문제를 해결해주자.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, K;
int arr[10002];
int lentosg[2201];
vector<int> sg[10002];
int kfirst, klast, kmx, kmn, nmx, nmn = 1000000007;
int total;
int mxL, mxM, mxR, mnL, mnM, mnR;
bool comp(int& x, int& y) {
return arr[x] < arr[y];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
cin >> arr[1];
int old = arr[1];
kmx = kmn = old;
for (int id = 2; id <= K; id++) {
int& cur = arr[id]; cin >> cur;
kmx = max(kmx, cur), kmn = min(kmn, cur);
total += abs(cur - old);
if (old < cur) {
for (int i = old; i <= cur; i++) lentosg[i] = id;
}
else {
for (int i = cur; i <= old; i++) lentosg[i] = id;
}
old = cur;
}
kfirst = arr[1], klast = arr[K];
for (int i = 1000; i < kmn; i++) lentosg[i] = 0;
for (int i = kmx + 1; i < 2201; i++) lentosg[i] = 10001;
for (int id = K + 1; id <= N; id++) {
int& cur = arr[id]; cin >> cur;
nmx = max(nmx, cur), nmn = min(nmn, cur);
sg[lentosg[cur]].emplace_back(id);
}
if (nmx > kmx) mxL = nmx - kfirst, mxM = (nmx - kmx) * 2, mxR = nmx - klast;
if (nmn < kmn) mnL = kfirst - nmn, mnM = (kmn - nmn) * 2, mnR = klast - nmn;
if (mxL <= min(mxM, mxR) && mnM <= min(mnL, mnR)) {
cout << total + mxL + mnM << '\n';
sort(sg[10001].begin(), sg[10001].end(), comp);
for (auto iter = sg[10001].rbegin(); iter != sg[10001].rend(); iter++) cout << *iter << '\n';
cout << 1 << '\n';
for (int id = 2; id <= K; id++) {
if (id == lentosg[kmn]) {
sort(sg[0].begin(), sg[0].end(), comp);
for (auto& x : sg[0]) cout << x << '\n';
}
sort(sg[id].begin(), sg[id].end(), comp);
if (arr[id - 1] < arr[id]) {
for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
}
else {
for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
}
cout << id << '\n';
}
}
else if (mxL <= min(mxM, mxR) && mnR <= min(mnL, mnM)) {
cout << total + mxL + mnR << '\n';
sort(sg[10001].begin(), sg[10001].end(), comp);
for (auto iter = sg[10001].rbegin(); iter != sg[10001].rend(); iter++) cout << *iter << '\n';
cout << 1 << '\n';
for (int id = 2; id <= K; id++) {
sort(sg[id].begin(), sg[id].end(), comp);
if (arr[id - 1] < arr[id]) {
for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
}
else {
for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
}
cout << id << '\n';
}
sort(sg[0].begin(), sg[0].end(), comp);
for (auto iter = sg[0].rbegin(); iter != sg[0].rend(); iter++) cout << *iter << '\n';
}
else if (mxM <= min(mxL, mxR) && mnL <= min(mnM, mnR)) {
cout << total + mxM + mnL << '\n';
sort(sg[0].begin(), sg[0].end(), comp);
for (auto& x : sg[0]) cout << x << '\n';
cout << 1 << '\n';
for (int id = 2; id <= K; id++) {
if (id == lentosg[kmx]) {
sort(sg[10001].begin(), sg[10001].end(), comp);
for (auto& x : sg[10001]) cout << x << '\n';
}
sort(sg[id].begin(), sg[id].end(), comp);
if (arr[id - 1] < arr[id]) {
for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
}
else {
for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
}
cout << id << '\n';
}
}
else if (mxM <= min(mxL, mxR) && mnR <= min(mnL, mnM)) {
cout << total + mxM + mnR << '\n';
cout << 1 << '\n';
for (int id = 2; id <= K; id++) {
if (id == lentosg[kmx]) {
sort(sg[10001].begin(), sg[10001].end(), comp);
for (auto& x : sg[10001]) cout << x << '\n';
}
sort(sg[id].begin(), sg[id].end(), comp);
if (arr[id - 1] < arr[id]) {
for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
}
else {
for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
}
cout << id << '\n';
}
sort(sg[0].begin(), sg[0].end(), comp);
for (auto iter = sg[0].rbegin(); iter != sg[0].rend(); iter++) cout << *iter << '\n';
}
else if (mxR <= min(mxL, mxM) && mnL <= min(mnM, mnR)) {
cout << total + mxR + mnL << '\n';
sort(sg[0].begin(), sg[0].end(), comp);
for (auto& x : sg[0]) cout << x << '\n';
cout << 1 << '\n';
for (int id = 2; id <= K; id++) {
sort(sg[id].begin(), sg[id].end(), comp);
if (arr[id - 1] < arr[id]) {
for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
}
else {
for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
}
cout << id << '\n';
}
sort(sg[10001].begin(), sg[10001].end(), comp);
for (auto& x : sg[10001]) cout << x << '\n';
}
else if (mxR <= min(mxL, mxM) && mnM <= min(mnL, mnR)) {
cout << total + mxR + mnM << '\n';
cout << 1 << '\n';
for (int id = 2; id <= K; id++) {
if (id == lentosg[kmn]) {
sort(sg[0].begin(), sg[0].end(), comp);
for (auto& x : sg[0]) cout << x << '\n';
}
sort(sg[id].begin(), sg[id].end(), comp);
if (arr[id - 1] < arr[id]) {
for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
}
else {
for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
}
cout << id << '\n';
}
sort(sg[10001].begin(), sg[10001].end(), comp);
for (auto& x : sg[10001]) cout << x << '\n';
}
else {
cout << total + mxM + mnM << '\n';
cout << 1 << '\n';
for (int id = 2; id <= K; id++) {
if (id == lentosg[kmx]) {
sort(sg[10001].begin(), sg[10001].end(), comp);
for (auto& x : sg[10001]) cout << x << '\n';
}
if (id == lentosg[kmn]) {
sort(sg[0].begin(), sg[0].end(), comp);
for (auto& x : sg[0]) cout << x << '\n';
}
sort(sg[id].begin(), sg[id].end(), comp);
if (arr[id - 1] < arr[id]) {
for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
}
else {
for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
}
cout << id << '\n';
}
}
}
같은 열의 두 높이 h1 < h2에 대하여, h2의 높이에 물건을 집을 수 있다면 h1의 높이에 있는 물건 또한 집을 수 있음을 관찰할 수 있다. 따라서 같은 열에 물건이 여럿 있다면 더 높은 위치에 있는 물건만을 고려해 문제를 풀어도 충분하다. 그러므로 이제부터는 각 열마다 접근해야 하는 가장 높은 위치(없다면 0)만을 고려해 문제를 해결하도록 하자.
dp[r][c]를 "c열에서 높이 r까지 접근 가능한 사다리를 설치한 경우, c열 이하의 모든 열의 꺼내야 할 물건을 모두 꺼내기 위한 최소비용"으로 정의하자.
이 dp[r][c]의 값은 (1) c열에 설치한 높이 r의 사다리가 c열에 있는 물건에 접근할 수 있는지, 접근할 수 있다면 (2) c-1열에 있는 물건 또한 접근할 수 있는지의 여부에 따라 c-1, c-2열의 dp값을 이용해 계산해낼 수 있음을 관찰할 수 있다.
위 관찰을 이용해 dp[r][c]의 값을 구해내는 점화식을 찾아 문제를 해결하자.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
int R, C, N;
int col[102];
int dp[101][102];
int ans = 1000000007;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> C >> R >> N; C++;
while (N--) {
int A, B; cin >> A >> B; A++;
col[A] = max(col[A], B);
}
for (int r = 0; r <= R; r++) {
dp[r][0] = dp[r][1] = r;
for (int c = 2; c <= C; c++) {
dp[r][c] = 1000000007;
}
}
//dp[r][c] : c열에 r짜리 막대를 놓은 상황. 이 때 c열까지를 완전히 채울 때의 최솟값
for (int c = 1; c <= C; c++) {
for (int r = 0; r <= R; r++) {
if (r < col[c]) {
for (int rr = col[c]; rr <= R; rr++) {
dp[r][c] = min(dp[r][c], dp[rr][c - 1] + r);
}
}
// 아래는 이제 r>=col[c] 성립
else if (r < col[c - 1]) {
for (int rr = 0; rr <= R; rr++) {
dp[r][c] = min(dp[r][c], dp[rr][c - 1] + r);
}
}
else {
for (int rr = 0; rr < R; rr++) {
dp[r][c] = min(dp[r][c], dp[rr][c - 2] + r);
}
}
}
}
for (int r = 0; r <= R; r++) ans = min(ans, dp[r][C]);
cout << ans;
}
이 글에서 op는 연산자 문자('#' 또는 '$')를 의미하고, X와 Y는 표현식을 나타내는 문자로 사용하겠다.
주어지는 표현식은 "A", "B"를 제외하면 항상 "(ext op exp)"와 같은 형태로 구성되어 있음을 관찰하자.
위의 관찰을 이용하면, 다음과 같은 세 가지를 할 수 있다면 문제를 충분히 해결할 수 있음을 발견할 수 있다.
(1) 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 A A B로 교체하기
(2) 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 B A B로 교체하기
(3) 리스트의 끝이 X Y A B와 같이 주어져있을 때 그 위치의 리스트를 (X op Y) A B로 교체하기
위 세 가지를 하는 방법의 자세한 설명은 생략하도록 하겠다. 다만 아래의 코드에 가능한 방법중 하나가 나와있으므로 전혀 방법을 못 찾겠다면 참고해보자.
위의 세가지가 가능하다면, 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 X A B로 교체하는 함수 f(X)를 고안해낼 수 있다. 구체적으로 X가 A와 같다면 (1)을, B와 같다면 (2)를, (P op Q)와 같다면 f(P), f(Q) 및 (3)을 순서대로 호출하는 것으로 리스트의 끝이 A B와 같을 때 이를 X A B로 바꿀 수 있다.
이와 같은 함수 f를 이용해 A B를 exp A B로 바꾸고, DROP을 2회 실행해 문제를 해결하자.
위와 같은 방법이 문제의 제약(리스트의 원소의 최대개수가 100, 총 1만번의 연산만 수행 가능)을 만족하는지를 확인하는 것은 간단하므로 서술을 생략한다.