중학교때 잠깐 봤었던거 같은 문제
[원석방 산하 폐수방] 1일차 셋 div 2 A번이다.
https://www.acmicpc.net/problem/2666
2666번: 벽장문의 이동
첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들
www.acmicpc.net
일단 간단한 그림을 그려보든지 해서 알수 있는 정보는
벽장문을 옮길때, 횟수는 그냥
A번 벽장을 B번 벽장으로 옮기고자할때 abs(A-B) 이다.
사이에 C번벽장이 있더라도 이는 동일하다.
여기서 좀 이상한 사고를 거쳐서,
브루트포싱하자는 의견에 도달했다.
벽장 두개가 기본적으로 주어져있고,
열려있는 벽장의 갯수가 추가될수 없다.
그렇다면, K번 벽장을 열고자 할때,
기존의 A번 벽장과 B번 벽장이 열려있다면
적당히 이동해 K번 벽장을 열고 난 뒤의 상태는 (K번, A번) || (K번, B번) 이 될 것이다.
즉 벽장 하나를 열고자 할때마다 경우의 수가 2배로 늘어나는데,
문제에서 제시하고 있는 상한값은 20번이므로
전체 경우의 수는 2^20 => 1048576 회이므로
TLE 없이 문제를 해결할수있다.
세그트리 구현할때 N*2 랑 N*2+1 으로 갈라지던게 생각이 나서,
트리같은느낌으로 구현해봤다
그냥 queue를 박던지 방법은 다양하게 시도해볼수있을듯?
배열크기는 최종값 저장하려면 2^21 보다 크게 잡아야한다
그냥 무지성으로 4백만정도 잡았다.
#include <bits/stdc++.h>
using namespace std;
int dp[4000000][3];
// 0 - bookshelf 1 a
// 1 - bookshelf 2 b ( a < b )
// 2 - cnt
int main(){
cin.sync_with_stdio(false);
cin.tie(NULL);
int N,M;
int a,b,k;
cin >> N;
cin >> a >> b;
if(a>b) { dp[1][0] = b; dp[1][1] = a; dp[1][2] = 0; }
else { dp[1][0] = a; dp[1][1] = b; dp[1][2] = 0; }
cin >> M;
for(int i=1; i<=M; i++){
cin >> k;
for(int j=(1<<(i-1)); j<(1<<(i)); j++){
// ( a, b ) -> ( a, k )
dp[j*2][0] = min(dp[j][0], k);
dp[j*2][1] = max(dp[j][0], k);
dp[j*2][2] = dp[j][2] + abs( dp[j][1] - k );
// ( a, b ) -> ( b, k )
dp[j*2+1][0] = min(dp[j][1], k);
dp[j*2+1][1] = max(dp[j][1], k);
dp[j*2+1][2] = dp[j][2] + abs( dp[j][0] - k );
}
}
int ans = 998244353;
for(int i=(1<<(M)); i<(1<<(M+1)); i++){
ans = min(ans, dp[i][2]);
}
cout << ans;
return 0;
}탈알고한지가 제법 오래되서 걱정했는데
아직도 골드하위 자력솔이 되긴 되는구만
조금 안심했다.