백준(BOJ) 25401 - 카드바꾸기

생각보다 어려운 문제였다.

카드들이 나열되어있고, 나열된 카드들의 숫자를 최소한으로 바꿔 등차수열을 만들거나/ 모두 같은 수로 만드는 것.

이 때 최소한의 교환 횟수를 출력해야한다.

사실 모두 같은 수로 만든다는 것은, 등차가 0인 수열로 만든다는 뜻도 된다. 따라서 최소한의 교환 횟수로 등차수열을 만든다고 생각하면 된다.

 

처음 풀 때 당연하게 생각하지만 놓치기 쉬운 부분이 하나 있었다.

=> 카드의 자리는 바꿀 수 없다. 각 카드에는 번호가 매겨져있다. 유의하자.

1. 두 수를 선택하고, 해당 두 수에 맞춰 등차수열로 만든다.(정답)

한 문장만 보면 이해하기 어려운데, 예를 들어보자.

수열

1 3 8 11 13가 있다고 가정한다.

여기서 두 개의 수를 선택해야 하는데, 3과 11을 선택했다고 가정해본다.

첫째항을 a, 등차를 d로 둬보자.

1부터 시작하는 등차수열이라고 생각해보면, 3은 둘째항이므로 a + d이다.

11는 4번째 항이므로 a + 3d이다.

d를 구하려면, 두 항에 공통적으로 속한 a를 소거해야 하므로 a + 3d - (a + d) = 11 - 3과 같이 구할 수 있다.

2d = 8 => d = 4로 구할 수 있다.

이렇게 두 수를 선택해 일정한 d를 구한 후, 해당 d에 맞춰 리스트를 바꿔본다.

등차가 4이면서 3과 11을 고정시킨 등차수열이면, 첫째항의 값은 3 - d = -1이어야 한다.

따라서 -1부터 등차인 4를 더해가며 해당 리스트에서 값을 체크해주면, 몇 개의 숫자를 바꿔야 할지 알 수 있다.

추가적으로 카드의 수는 정수로만 바꿀 수 있으므로, d가 소수가 되는 경우에는(위에서 d를 구할 때 나누어 떨어지지 않는 경우) 경우의 수에서 제외한다.

 

시간 복잡도

O(N^3)

1. 500개 중 2개 선택 => 500C2 = 124750 O(N^2)

2. 각 선택 시 O(N)만큼 탐색하며 바꿔야 할 카드의 수 계산

    public static int cntChange(int[] nums, int startValue, int diff) {
        int count = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != startValue) count++;
            startValue += diff;
        }
        return count;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] nums = new int[N + 1];
        int minAnswer = 500;
        for (int i = 1; i < nums.length; i++) nums[i] = Integer.parseInt(st.nextToken());
        for (int i = 1; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                float diff = (float)(nums[j] - nums[i]) / (j - i);
                if (diff != (int)diff) continue;
                minAnswer = Math.min(minAnswer, cntChange(nums, nums[i] - ((i - 1) * (int)diff), (int)diff));
            }
        }
        System.out.println(minAnswer);
    }

 

2. 실패한 아이디어

아이디어 : 최소한의 교환 횟수를 가져가려면, 최대한 각 카드의 숫자를 바꾸려고 건드리지 않아야 한다.

그러므로, 각 카드간의 등차를 다 구해본 후 해당 등차에 맞게 모든 리스트를 조정한다.

        Set<Integer> possDiff = new HashSet<>();
        for (int i = 0; i < nums.length - 1; i++) possDiff.add(nums[i + 1] - nums[i]);
        possDiff.add(0);
        for (int diff : possDiff) { // diff : targetDiff. 해당 등차로 만들어야 함.
            for (int i = 0; i < nums.length; i++) { // 중심이 될 수
                int[] tempNums = nums.clone();
                int subAnswer = 0;
                for (int j = i; j < nums.length - 1; j++) {
                    if (tempNums[j] + diff != tempNums[j + 1]) {
                        subAnswer++;
                        tempNums[j + 1] = tempNums[j] + diff;
                    }
                }
                for (int j = i; j > 0; j--) {
                    if (tempNums[j] - diff != tempNums[j - 1]) {
                        subAnswer++;
                        tempNums[j - 1] = tempNums[j] - diff;
                    }
                }
                if (subAnswer < minAnswer) minAnswer = subAnswer;
                if (diff == 0) break;
            }
        }

 

실패 사유 : 모든 경우의 수를 커버 할 수 없다. 바로 옆에 있는 수와의 등차만 경우의 수로 생각했기 때문.

그렇다고 해서 두 수를 선택하는 경우를 모두 생각해본다면, 시간초과가 난다.(두 수를 선택한다고 해도 위와 같이 항의 위치에따라 등차를 구하지 않았기 때문에 오답이다.)

혹시나 두 수를 선택하고, 등차도 제대로 구했다고 생각해본다면

500C2 => 124,750

각 경우의 수 마다 리스트 만들기 O(n^2) => 250,000

124,850 * 250,000 = 31,187,500,000 시간초과.

실제로 하나씩 바꾸면서 체크하는것이 아니라 각 항에 들어가야 할 수를 정확히 구한 후 바꿔야 할 카드 개수를 세야 효율적이다.