[JAVA] 백준 (골드5) 25401번 카드 바꾸기

링크

https://www.acmicpc.net/problem/25401

---

입력 예제

4
1 2 2 4

---

출력 예제

1

---

풀이

N개의 카드가 등차수열을 이루어야 되는 문제이다. 우선 여기서 필요한 등차수열의 공식은 다음과 같다.

• $a_n = a_1 + (n-1)d$
• $d = \frac{a_n - a_1}{n - 1}$

모든 카드 쌍으로 만들 수 있는 공차로 등차수열을 만든 다음, 카드와 비교하여 다른 수가 최소가 될 때를 구하면 된다. 이때 초항도 모든 카드의 숫자가 될 수 있다.

또한 N의 최대가 500이므로 시간복잡도는 $O(n^3)$으로 충분히 브루트 포스로 해결할 수 있다.

전체 코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
백준 / 카드 바꾸기 / 골드5
https://www.acmicpc.net/problem/25401
 */
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("wda067/io/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());  //2 ~ 500
        int[] cards = new int[N];  //-1,000,000 ~ 1,000,000

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        int min = N - 1;  //최대 변경 횟수

        //모든 카드 쌍으로 가능한 공차 탐색
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int diff = cards[j] - cards[i];
                int dist = j - i;

                //a1 = 3, a3 = 7일 경우
                //공차는 (7 - 3) / 2
                int d = diff / dist;
                int count = 0;

                //현재 공차를 기준으로 등차수열 생성
                for (int n = 0; n < N; n++) {
                    int a1 = cards[i];  //초항
                    //등차수열의 일반항
                    int an = a1 + (n - i) * d;
                    if (cards[n] != an) {
                        count++;
                    }
                }

                min = Math.min(min, count);
            }
        }

        System.out.println(min);
    }
}