Baekjoon 16951. 블록 놀이 / Java

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

알고리즘 설명

문제 설명

각기 다른 높이를 가진 배열을 높이 차를 k로 만드는 문제

코드 설명

한 번에 몇개를 옮기든 하나의 블록의 높이를 바꾸는 시간은 동일하기 때문에, 하나의 블록을 고정해 놓고 완전 탐색을 하면 된다.
n < 1000 이기 때문에, 시간 복잡도 O(n ^ 2)이므로 경우의 수는 1,000,000가지밖에 안된다

ㄴ

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static int n;
    public static int k;
    public static int[] arr;
    public static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        sol(arr, n, k);
        System.out.println(answer);
    }

    private static void sol(int[] arr, int n, int k) {
        for (int i = 0; i < n; i++) {
            int[] res = new int[n];
            res[i] = arr[i];

            // 블록의 왼쪽
            boolean flag = false;
            for (int j = i - 1; j >= 0; j--) {
                res[j] = res[j + 1] - k;
                // 높이가 0보다 작아지면 스킵
                if (res[j] <= 0) {
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                // 블록의 오른쪽
                for (int j = i + 1; j < n; j++) {
                    res[j] = res[j - 1] + k;
                }

                // 원래 블록과 높이가 다른 블록 개수를 체크
                int cnt = 0;
                for (int j = 0; j < n; j++) {
                    if (arr[j] != res[j]) {
                        cnt++;
                    }
                }
                answer = Math.min(answer, cnt);
            }
        }
    }
}