[코드트리/NOVICE MID] 움직이는 블록 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
       
        int total = 0;
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            total += arr[i];
        }
 
        int target = total / N;
         int cnt = 0;    // 움직여야 할 최소 블럭 수
 
        for(int i = 0 ; i < N ; i++) {
            if(arr[i] == target) continue;
 
            if(arr[i] < target) {
                for(int j = i + 1 ; j < N ; j++) {
                    if(arr[j] > target) {
                        int diff = Math.min(target - arr[i], arr[j] - target);
                        arr[i] += diff;
                        arr[j] -= diff;
                        cnt += diff;
                    }
                }
            }
            else if(arr[i] > target) {
                for(int j = i + 1 ; j < N ; j++) {
                    if(arr[j] < target) {
                        int diff = Math.min(arr[i] - target, target - arr[j]);
                        arr[i] -= diff;
                        arr[j] += diff;
                        cnt += diff;
                    }
                }
            }
        }
 
        System.out.println(cnt);
    }
}

 

 

 

🧩  해결 아이디어

• 그리디

평균 블록 수보다 많은 곳에서 적은 곳으로 옮기는 것이 최적의 방법

- 평균 블록 수보다 더 큰 블럭에 대해서만 그 차이만큼 옮김

 

 

---

🔺 다른 풀이들

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int[] blocks = new int[n];
 
        int sumOfBlocks = 0;    // 전체 블럭 수
 
        for(int i = 0; i < n; i++) {
            blocks[i] = sc.nextInt();
            sumOfBlocks += blocks[i];
        }
        
        // 평균 블럭 수 보다 더 큰 블럭에 대해서만 그 차이만큼 옮김
        int avg = sumOfBlocks / n;
        int ans = 0;
 
        for(int i = 0; i < n; i++)
            if(blocks[i] > avg)
                ans += blocks[i] - avg;
 
        System.out.print(ans);
    }
}

 

 

---

💬 느낀 점

와하하하 쉬운 문제를 어렵게 생각했다네요............

 

1회독	2회독	3회독	4회독	5회독
V