[소프티어] 진정한 효도(JAVA)

27200 2025. 3. 20. 17:32

문제

풀이(40분)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] grid = new int[3][3];

        // 입력 받기
        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int minCost = Integer.MAX_VALUE;

        // 가로, 세로 3칸씩 검사
        for (int i = 0; i < 3; i++) {
            minCost = Math.min(minCost, calculateCost(grid, i, 0, i, 2)); // 가로
            minCost = Math.min(minCost, calculateCost(grid, 0, i, 2, i)); // 세로
        }

        System.out.println(minCost);
    }

    // 주어진 3칸의 숫자를 같은 값으로 만드는 비용 계산
    static int calculateCost(int[][] grid, int x1, int y1, int x2, int y2) {
        int[] values = new int[3];
        int index = 0;

        // 3개의 값을 배열에 저장
        for (int i = x1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                values[index++] = grid[i][j];
            }
        }

        Arrays.sort(values);

        int minCost = Integer.MAX_VALUE;

        // 1, 2, 3 중 하나로 변환할 때 비용 계산
        for (int target = 1; target <= 3; target++) {
            int cost = 0;
            for (int i = 0; i < 3; i++) {
                cost += Math.abs(values[i] - target);
            }
            minCost = Math.min(minCost, cost);
        }

        return minCost;
    }
}

문제 풀이 전략

사실 간단한 코드다.

농장의 크기가 3x3으로 지정되어 있고, 입력도 1~3까지이기 때문에 브루트포스로 모두 구해보면 되는 것이다.

정리하자면 모든 행과 열에서 1,2,3중 어떤 값으로 변환했을 때 최소가 되는지에 대해 27가지를 모두 저장한 뒤 최소를 뽑아내면 된다.

하지만 문제를 푸는 데 있어 40분이나 소요된 것은 그 외에 조건이 확장된다면 어떻게 해야 할지를 고민해 보았다.

대표적으로 평균값과 중앙값 사이에서 고민을 했다.

일반적으로 숫자를 맞추라는 것은 평균(반올림, 올림, 내림 등을 거쳐)을 구한 뒤 이에 맞추면 된다. 문제의 1,1,3을 보면 1로 맞추어 2로 변경하는 것이 최솟값이 된다. 즉, 평균값이 아닌(여기서 평균은 반올림을 했다.) 중앙값을 구하라는 것이다.

그럼 평균(내림)을 하면 되는 거 아닐까?라는 고민도 해보았지만 반례가 존재했다.

중앙값은 완벽한가에 대해서도 길이가 짝수라면?이라는 고민이 되었다.

즉, 동일하게 1~3의 숫자만 입력된다!라고 한다면 단순히 1~3을 모두 해보는 것이 더 좋을 수도 있다는 뜻이다.

수학적으로 정확한 결론은 못 내렸지만 조건의 확장을 고민해 보고, 가끔은 단순한 검사가 더 효율적일 수도 있다는 결론을 얻을 수 있었다.