VendingMachine

Code

public class VendingMachine

{

    int rows, cols;

    int ts;                // a total of seconds

    int ci, cj;            // current i, current j;

    int[][] p;

    void addSecs(int nj) {

        int a = Math.abs(nj - cj);

        int b = cols - Math.abs(nj - cj);

        ts += (a < b) ? a : b;

    }

    void setMaxCol() {

        int max = -1, mj = cj;

        for (int j = 0; j < cols; j++) {

            int sum = 0;

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

                if (p[i][j] > 0) sum += p[i][j];

            if (sum > max) {max = sum; mj = j;}

        }

        if (mj != cj) {addSecs(mj); cj = mj;}

    }

    public int motorUse(String[] prices, String[] purchases) {

        rows = prices.length;

        cols = prices[0].split(" ").length;

        int pcLen = purchases.length;

        ts = 0;

        p = new int[rows][];

        int[][] pc = new int[pcLen][3];

        int[] t = new int[pcLen];

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

            String[] sp = prices[i].split(" ");

            p[i] = new int[cols];

            for (int j = 0; j < cols; j++)

                p[i][j] = Integer.parseInt(sp[j]);

        }

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

            String[] sp = purchases[i].split("[:,]");

            for (int j = 0; j < 3; j++)

                pc[i][j] = Integer.parseInt(sp[j]);

        }

        t[0] = 5;

        for (int i = 1; i < pcLen; i++)

            t[i] = pc[i][2] - pc[i-1][2];

        ci = 0; cj = 0;

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

            if (t[i]>=5) setMaxCol();

            addSecs(pc[i][1]);

            ci = pc[i][0] ; cj = pc[i][1];

            if (p[ci][cj] == 0) return -1;

            p[ci][cj] = 0;

        }

        setMaxCol();

        return ts;

    }

}

Problem

미판매 시간이 5분이 넘으면 열에 있는 모든 상품들의 가격의 합이 가장 큰 열로 회전 원통(rotating cylinder: 상품을 꺼내주는 부품)이 이동하는 자동 판매기가 있다. 기계 가동 후 회전 원통은 (0,0)으로 초기화 되고, 이후에 가장 잘 팔리는 상품열로 이동한다. 마지막 판매 후에 한 번 더 가장 잘 팔리는 상품열로 이동한다. 현재 열에서 바로 이전 열 또는 바로 다음 열로 넘어갈 때 1초가 걸린다 (선반을 이동할 때는 시간이 걸리지 않는다). 회전 원통은 순환이 가능하므로 가장 가까운 방향을 이용해 해당 열로 이동한다 (0열에서 끝열로 이동할 때 순환이 가능하므로 왼쪽으로 이동하면 1초가 걸린다). 구매자가 해당 상품의 모든 수량을 구매한다고 가정하고, 상품이 팔리면 가격을 0으로 설정한다. 구매자들이 물건을 구매한 후, 자동 판매기 회전 원통이 이동한 총 시간을 구해야 한다.

Explanation

문제를 제대로 이해하면 금방 풀 수 있는 알고리즘이고 코드 또한 쉬우므로 설명은 생략한다.