문제 설명은 생략한다.
예시에서 2번,5번 벽장이 열려있고 3번,1번,6번,5번 순으로 벽장을 열어야 할 경우를 생각해보면 경우에 대해 표로 나타낼 수 있다.
<>내부에 들어있는 숫자는 벽장을 열어야하는 순서 index이다. (<1>은 3번 벽장, <2>는 1번벽장)
벽장을 순서에 맞게 열 경우마다 그다음 경우는 2가지씩 생긴다. 따라서 완전 탐색을 통해 모든 경우를 따져보면 된다.
DP[N][M] : N번 벽장을 열 때 최소 이동횟수 (M은 열려있는 나머지 벽장 정보)
N번 벽장과 나머지 벽장이 일치하는 경우는 제외하고 경우를 저장하고 이미 열어본적있는 벽장에 대한 정보는 최솟값을 구해 다시 저장하는게 포인트
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[21][21]; //벽장 순서index, 나머지 벽장번호
int T, op[2]; //벽장 개수, 열려있는 벽장번호(0,1)
int lf,L[21]; //열어야하는 벽장 순서개수, 열어야하는 벽장순서 배열
int main(){
scanf("%d%d%d%d", &T, &op[0], &op[1],&lf);
for (int n = 1; n <= lf; n++)
scanf("%d", &L[n]);
for (int n = 1; n < 21; n++)
for (int m = 1; m < 21; m++)
dp[n][m] = -1;
dp[1][op[1]] = abs(op[0] - L[1]);
dp[1][op[0]] = abs(op[1] - L[1]);
for (int n = 1; n < lf; n++){ //algorithm start
for (int m = 1; m <= T; m++){
if (dp[n][m] != -1 && L[n] != m){
int first, second;
first = dp[n][m] + abs(L[n] - L[n + 1]);
second = dp[n][m] + abs(m - L[n + 1]);
if (dp[n + 1][m] != -1){
first = min(dp[n + 1][m], first);
}
if (dp[n + 1][L[n]] != -1){
second = min(dp[n + 1][L[n]], second);
}
dp[n + 1][m] = first;
dp[n + 1][L[n]] = second;
}
}
}
int ans = 987654321;
for (int n = 1; n <= T; n++){
if (dp[lf][n] != -1)
ans = min(ans, dp[lf][n]);
}
printf("%d\n", ans);
return 0;
}
| cs |
ctrl c
답글삭제ctrl v
ok 통과