- 문제 다운받기

invalid-file

이번문제는 굉장히 쉬운 문제다. 모든 경우를 다 고려해도 6가지 경우밖에 나오지 않는다. 지금 붙여넣은 소스는 약간 길다. 이유는 먼저 입력받는 코드를 c++에서는 cin으로 받으면 되지만 JAVA는 UVA에서 지정한 함수를 사용해서 받아야한다. 아래 readLn method가 바로 그것이다.

또한 순열의 개수가 적기때문에 code로 박지 않고 재귀함수를 돌려 순열을 모두 생성하였다. 이는, 코드가 길어지고 시간이 약간 느려지지만 앞으로의 문제풀이를 위한 연습으로써 일부러 해봤다. 시간을 줄이고 싶다면 6가지 순열을 코드에 박아버리는 방법도 좋다. 개수가 적으니까 코드에 해당하는 결과 문자열 6개도 같이 박아놓으면 소스가 굉장히 짧아지고 속도도 나름대로 괜찮다.

minimum을 계산할 결과값 6개도 for문이나 어떠한 함수 없이 바로 계산할 수도 있는 문제이다. 경우의 수가 얼마 없으니까.

import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
        public static String readLn (int maxLg) {
                byte lin[] = new byte [maxLg];
                int lg = 0, car = -1;

                try {
                        while (lg < maxLg) {
                                car = System.in.read();
                                if ((car < 0) || (car == '\n')) break;
                                lin [lg++] += car;
                        }
                }
                catch (IOException e) {
                        return (null);
                }

                if ((car < 0) && (lg == 0)) return (null);
                return (new String (lin, 0, lg));
        }
        
        int[][] nBottle;       // 병들을 담을 초기값
        int nResult;           // minimum move 수
        String minStr;          // minimum일 때 String의 값
       
        public Main() {               
                nBottle = new int[3][3];
               
                String line;
                while ((line = readLn(255)) != null) {
                        nResult = Integer.MAX_VALUE;
                        StringTokenizer in = new StringTokenizer(line);
                       
                        int i,j;
                        for(i=0 ; i<3 ; i++)
                                for(j=0 ; j<3 ; j++)
                                        nBottle[i][j] = Integer.parseInt(in.nextToken());
                       
                        // 초기값을 0, 1, 2로 하는 순열을 생성하고 계산을 수행한다.
                        runPermute(new int[] {0,1,2}, 0);
                       
                        // 결과를 출력한다.
                        System.out.println(minStr + " " + nResult);
                }
        }
       
        /**
         * 길이가 3인 순열을 생성한 후 minimum move를 계산한다.
         * @param bottles 병들의 순열값
         * @param index 시작 index
         */
        private void runPermute(int[] bottles, int index) {
                if(index == 3)
                        calculateAmount(bottles);
               
                int i;
                for(i=index ; i<3 ; i++) {
                        swap(bottles, i, index);
                        runPermute(bottles, index+1);
                        swap(bottles, i, index);
                }
        }
       
        /**
         * 입력받은 bottles로 minimum move를 계산한다.
         * @param bottles
         */
        private void calculateAmount(int[] bottles) {
                int i, j;
                int amount = 0;
                for(i=0 ; i<3 ; i++) {
                        for(j=0 ; j<3 ; j++) {
                                if(i == j)
                                        continue;
                                amount += nBottle[j][bottles[i]];
                        }
                }
               
                String tmpStr = "";
                for(i=0 ; i<3 ; i++)
                        tmpStr += convertToString(bottles[i]);
               
                if(nResult == amount) {
                        if(minStr.compareTo(tmpStr) > 0)
                                minStr = tmpStr;
                }
                else if(nResult > amount) {
                        nResult = amount;
                        minStr = tmpStr;
                }
        }
       
        /**
         * bottles의 pos1과 pos2의 위치의 값을 변경한다.
         * @param bottles
         * @param pos1
         * @param pos2
         */
        private void swap(int[] bottles, int pos1, int pos2) {
                int temp;
               
                temp = bottles[pos1];
                bottles[pos1] = bottles[pos2];
                bottles[pos2] = temp;
        }
       
        /**
         * num을 문자값으로 변환시킨다.
         * @param num
         * @return
         */
        private String convertToString(int num) {
                switch(num) {
                case 0 : return "B";
                case 1 : return "G";
                case 2 : return "C";
                }
                return "";
        }
       
        public static void main(String[] args) {
                new Main();
        }
}

이올린에 북마크하기