[C/C++] 백준 11092 Safe Passage

11092 Safe Passage

11092번: Safe Passage

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> list;

int DP (int e) {
    if(e == 1) return list[1];
    if(e == 0) return 0;
    return min(list[1] + list[0] + list[e] + list[1] + DP(e-2), list[e] + list[0] + DP(e-1));
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        list.push_back(x);
    }
    sort(list.begin(), list.end());
    cout << DP(n-1);

    return 0;
}

 

확실히 알 수 있는 것은 투명 망토를 전달해 주기 위해 기숙사에서 학교 입구로 돌아갈 때는 해당 시점에 기숙사에 있던 사람 중 가장 빠른 사람이 가야 한다는 것이다.

-> 문제는 학교 입구에서 기숙사로 들어갈 때 짝지을 2명을 고르는 방법이다.

i) 먼저 생각나는 방식은 시간이 오래 걸리는 사람은 오래 걸리는 사람들끼리, 적게 걸리는 사람은 적게 걸리는 사람들끼리 묶는 것이다.

이 방식을 택했을 때 어느 정도 맞는 듯해 보이지만, 문제가 생긴다.

만약 입력 값이 "5 4 100 101 102 103" 이라면, 위의 방식으로는 최솟값을 구할 수 없다.
이 예시의 최소 값은 418으로,

ii) 4와 100이 건너갔다 4가 되돌아오고, 다시 4와 101이 건너갔다 4가 되돌아오고, 4와 102가 건너갔다 4가 되돌아오고... 식이다.
(4 x 3 + 100 + 101 + 102 + 103 = 418)

 

따라서 위의 i), ii) 두 가지 방법 중 최소 비용의 경우를 선택해야 한다. 재귀를 이용해 풀었는데, 일단 학생들을 오름차순으로 정렬한다.

-> list[0], list[1]은 자동적으로 가장 빠른 2명의 학생을 의미하게 된다.

 

함수 DP(e)의 의미는, 0번째부터 e번째까지의 학생을 옮기는 데 드는 최소 비용을 구하는 것이다.

 

i)의 방식:

맨 처음 0번째, 1번째 학생이 건너가는 시간 list[1], 0번째 학생이 투명망토를 들고 돌아오는 시간 list[0]이 든다.

이제 가장 오래 걸리는 2명 (list[e], list[e-1])이 기숙사에 가는데 시간이 list[e]만큼 들고, 기숙사에 있는 사람 중 가장 빠른 학생이 list[1]이므로 망토를 되돌려주는데 그만큼 비용이 든다.

-> list[1] + list[0] + list[e] + list[1]

최종적으로 학교 문 앞에 0 ~ e-2번째 학생이 있게 된다. 이제 이 경우는 DP(e-2)로 처리할 수 있다.

드는 시간: list[1] + list[0] + list[e] + list[1] + DP(e-1)

 

ii)의 방식:

가장 빠른 사람(list[0]), 가장 느린 사람(list[e])이 짝지어 기숙사로 들어가고, 기숙사에서 가장 빠른 사람이 다시 투명망토를 건네러 나온다. 최종적으로 학교 문 앞에 0번째부터 e-1번째 학생까지 있게 된다. 이제 이 경우는 DP(e-1)로 처리할 수 있다.

드는 시간: list[e] + list[0] + DP(e-1)

 

이제 i)와 ii) 중 적게 걸리는 방법을 재귀를 통해 계속 선택해 나가면 된다.

 

 

 

위의 소스 코드처럼 짤 수도 있으나, 반복문 형식으로 풀 수도 있을 것이다. 다음은 조금 더 개선된 방식의 풀이이다.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> list;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n;
    int i, res = 0;
    for (i = 0; i < n; ++i){
        cin >> x;
        list.push_back(x);
    }
    sort(list.begin(), list.end());
    for (i = n - 1; i > 1; i -= 2)
        res += min(list[0] + list[1] * 2 + list[i], list[0] * 2 + list[i - 1] + list[i]);

    if (i == 1) res += list[1];
    else res -= list[0];

    cout << res << '\n';

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

#define min(a, b) (((a) < (b)) ? (a) : (b))
int list[18];

int comp(const void *a, const void *b) {
    int num1 = *(int *) a;
    int num2 = *(int *) b;
    if (num1 < num2) return -1;
    if (num1 > num2) return 1;
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    int i, res = 0;
    for (i = 0; i < n; ++i)
        scanf("%d", &list[i]);

    qsort(list, n, sizeof(int), comp);
    for (i = n - 1; i > 1; i -= 2)
        res += min(list[0] + list[1] * 2 + list[i], list[0] * 2 + list[i - 1] + list[i]);

    if (i == 1) res += list[1];
    else res -= list[0];

    printf("%d\n", res);

    return 0;
}

 

막상 제출하고 보니, 메모리와 시간 측면에서 유의미한 차이를 보이지 않았다. 입력이 최대 15개 정도밖에 없어서인 것 같다.