백준 16951 자바 - 블록 놀이 (BOJ 16951 JAVA)

문제 : boj16951

 

 

1. 우선 제한을 한번 봐보자.

  A_i가 최대 1000인데 N과 K도 최대 1000이다. 그럼 N이 1000이고, K도 1000이라면 A_1000은 못해도 1+999x1000은 되어줘야 하는데 A_i의 최대값은 1000이다! 그러니 좀 헷갈릴 수 있는데, 그냥 주어진대로 생각해보면 된다. 결국 저건 문제 난이도를 떨어뜨리기 위한 조건으로 결국 A_1의 값이 1~1000이라는 말과 마찬가지가 된다.

 

 

2. '1'이 그래서 무슨 의미임?

  이 문제에서 각 A_i의 값을 다음과 나타낼 수 있다. 그리고 A_1의 값은 제한에 의해 1~1000으로 고정된다!

따라서 A_1을 1~1000까지 중 하나로 고정시켰을 때, 주어진 A_i들이 가장 많이 들어맞는 경우를 찾으면 답을 구할 수 있다는 얘기이다. A_1을 1000가지 중 하나로 변경해보면서, 총 1000개(N)의 배열을 확인해보면 되므로 최대 O(1000N)이면 풀 수 있다.

 

 

3. 예시

  예를들어 다음과 같은 입력을 봐보자.

4 2
1 2 8 10

  위의 입력에 대해 A_1을 1~1000으로 변경해가며 동일한 숫자가 가장 많은 개수를 세보면 A_1이 4일 때의 2개가 된다.

따라서 N-2 = 2가 답이 된다. 어차피 1분에 하나를 선택해서 무제한으로 늘리거나 줄일 수 있으므로 뭐 몇을 더해야한다, 몇을 빼야한다는 중요한 점이 아니다. 어긋나는게 몇개인지만 알면 된다.

 

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());

        int max = 0;
        for (int i = 1; i <= 1000; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] == i+j*k)
                    cnt++;
            }
            if (cnt>max) max = cnt;
        }
        System.out.println(n - max);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}