반응형

https://www.acmicpc.net/problem/2666

 

2666번: 벽장문의 이동

첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp [ i ][ j ][ k ]에서 i는 현재 순서, j는 현재 열려있는 1번 문, k는 현재 열려있는 2번 문입니다.

 

2. 다음과 같은 점화식을 세웁니다. 이때, o1은 1번 문, o2는 2번 문입니다.

dp[ i ][ j ][ k ] = min(abs(arr [num] - o1) + go(num + 1, arr [num], o2), abs(arr [num] - o2) + go(num + 1, o1, arr [num]))

 

3. 마지막에 go(0, o1, o2)를 출력해줍니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cmath>
#include<cstring>
 
using namespace std;
 
int N, M;
int o1, o2;
int arr[20];
int dp[20][21][21];    //[순서][1번문][2번분]
 
int go(int num, int o1, int o2)
{
    if (num >= M) {
        return 0;
    }
    if (dp[num][o1][o2] != -1) {
        return dp[num][o1][o2];
    }
    int& ret = dp[num][o1][o2];
    ret = min(abs(arr[num] - o1) + go(num + 1, arr[num], o2), abs(arr[num] - o2) + go(num + 1, o1, arr[num]));
    return ret;
}
 
int main()
{
    scanf("%d %d %d %d", &N, &o1, &o2, &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%d", &arr[i]);
    }
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", go(0, o1, o2));
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2229번 - 조 짜기 (C++)  (0) 2022.11.03
[ 백준 ] 2157번 - 여행 (C++)  (0) 2022.11.02
[ 백준 ] 2302번 - 극장 좌석 (C++)  (0) 2022.10.31
[ 백준 ] 1309번 - 동물원 (C++)  (0) 2022.10.30
[ 백준 ] 1965번 - 상자넣기 (C++)  (0) 2022.10.29

+ Recent posts

티스토리툴바