[소프티어 7374번] 진정한 효도

 

Softeer - 현대자동차그룹 SW인재확보플랫폼

import sys

input = sys.stdin.readline

# 남우 부모님의 농사일을 도우려고 함

# 남우에게 할당된 땅은 3x3 크기의 격자
# 1 <= 각 땅의 높이 <= 3

# 부모님이 농사지을 땅의 크기는 1x3
# 농사를 짓기 위해서는 해당 영역 내 땅의 높이가 전부 동일해야 함 !!!

# 따라서 특정 땅의 높이를 낮추거나 높여서 3x3 격자 내에 부모님이 농사지을 수
# 있는 영역이 최소 1군데 이상 생기도록 만들려고 함

# 남우가 특정 땅의 높이를 1만큼 낮추거나 높이는데 1만큼의 비용이 소요

# 부모님께서 농사를 지으실 수 있도록 땅을 일구기 위해 남우에게 필요한 최소비용

area = [list(map(int,input().split())) for _ in range(3)]

available = False

answer = float("inf")

def check_row(n):

    value = area[n][0]

    for i in range(1,3):
        if value != area[n][i]:
            return False

    return True

def check_col(n):

    value = area[0][n]

    for i in range(1,3):
        if value != area[i][n]:
            return False

    return True

for i in range(3):
    if check_row(i):
        available = True
    if check_col(i):
        available = True

def calculate_row(n):

    global answer

    row_set = set(area[n])

    if len(row_set) == 2:
        answer = min(answer, max(row_set) - min(row_set))
    else:
        mok = sum(row_set) // 3
        temp = sum([abs(x-mok) for x in row_set])
        answer = min(answer, temp)

def calculate_col(n):

    global answer

    col_set = set([area[x][n] for x in range(3)])

    if len(col_set) == 2:
        answer = min(answer, (max(col_set) - min(col_set)) )
    else:
        mok = sum(col_set) // 3
        temp = sum([abs(x-mok) for x in col_set])
        answer = min(answer, temp)

if available:
    print(0)
else:
    for i in range(3):
        calculate_row(i)
        calculate_col(i)
    print(answer)

 

이번 문제는 3x3 크기의 격자에서 1x3 크기의 영역 안의 값들이 모두 같은 블럭을 1개 이상 만들기 위해 필요한 최소 비용을 구하는 문제이다.

 

비용을 구하기에 앞서서 격자 중에서 값이 모두 같은 1x3 크기의 블럭이 있는지 확인하기 위해 가로와 세로 기준으로 점검하는 함수(check_row / check_col)을 선언하였고, 모든 행과 열을 순회하면서 점검해본 결과 존재할 경우(available) 곧바로 0을 출력하도록 구현하였다.

 

만약에 값이 모두 같은 1x3 크기의 블럭이 없다면 모든 행과 열에 대해서 값을 통일하기 위한 최소비용을 업데이트하는 함수(calculate_row / calculate_col)를 실행하였다.

 

본 함수의 로직은 다음과 같다.

• 3개의 값 중 2개의 값이 같고, 1개의 값만 다른 경우 : 1개의 값을 수정해주는 것이 최소 비용
• 3개의 값이 모두 다른 경우 : (모든 값의 합 // 3) 이 최소 비용