BridgeCrossing

Code

import java.util.Arrays;

public class BridgeCrossing

{

    int n, min;

    boolean[] a;

    int[] times;

    void go(int t, int num) {

        for (int i = 0; i < n; i++) {

            if (!a[i]) continue;

            a[i] = false;

            for (int j = i+1; j < n; j++) {

                if (!a[j]) continue;

                a[j] = false;

                if (num==2 && t+times[j]<min) min = t+times[j];

                for (int k = 0; k < n; k++) {

                    if (!a[k]) {

                        a[k] = true;

                        go(t+times[j]+times[k],num-1);

                        a[k] = false;

                        break;

                    }

                }

                a[j] = true;

            }

            a[i] = true;

        }

    }

    public int minTime(int[] _times) {

        if (_times.length == 1) return _times[0];

        times = _times;

        n = times.length;

        min = 1000;

        a = new boolean[n];

        for (int i = 0; i < n; i++)

            a[i] = true;

        Arrays.sort(times);

        go(0,n);

        return min;

    }

}

Problem

최대 6명의 사람이 최대 2명 밖에 건널 수 없는 낡은 다리를 건너야 한다. 어두운 밤이고 손전등은 한 개만 있다. 두 명이 건너고 난 후, 건넌 사람 중 한 명이 손전등을 주기 위해 다시 돌아가야 한다. 사람마다 건너는 시간이 같거나 다르며, 두 명의 사람이 같이 건널 때 더 시간이 오래 걸리는 사람의 시간이 걸린다. 모든 사람들이 다리를 건너는 최소 시간을 구하라.

Explanation

건널 때는 모든 사람 중 두 명을 뽑는 경우의 수를 구하고, 돌아올 때는 최소 시간을 가진 사람을 뽑으면 된다.