[골드 2] 백준 2450 - 모양 정돈 (파이썬)

분류 : 브루트포스

링크 : https://www.acmicpc.net/problem/2450

풀이

배열 A에는 1, 2, 3이 섞여있으면서, 각각 모양을 나타낸다.

이 배열을 구간 3개로 나누어서, 각 구간에는 한 가지 모양이 있도록 정렬해야 한다.

예를 들어서 [2, 2, 1, 1, 3, 3] 과 같은 형태이다.

단, 숫자들을 바꾸는 횟수를 최소화 해아한다.

입력 처리는 다음과 같다.

N = int(input())
A = list(map(int, input().split()))
A = [x - 1 for x in A]  # 0, 1, 2 로 바꿈

입력 배열을 x - 1을 통해서 0, 1, 2로 정규화한다.

그후 각 숫자의 개수를 센다.

count = [0] * 3
for x in A :
    count[x] += 1

예를 들어서 A = [0, 0, 1, 2, 1] → count = [2, 2, 1] 이다.

이후 순열을 통해 모든 배치를 시도한다.

for permutation in permutations(range(3), 3):

예를 들면 (0, 1, 2), (0, 2, 1) … 총 6가지 순서로 세 구간을 만들 수 있다.

구간을 미리 만들어 뒀으면 정렬된 상태의 목표 배열을 생성한다.

B = []
for x in permutation:
    B += [x] * count[x]

예를 들어서 count = [2, 2, 1] 이고, permutation = (1, 0, 2) 라면 B = [1, 1, 0, 0, 2]가 된다.

잘못 위치한 원소를 파악 하기 위해서 다음과 같디 정의 한다.

wrong = [[0]*3 for _ in range(3)]
for i in range(N):
    if A[i] != B[i]:
        wrong[A[i]][B[i]] += 1

wrong[i][j]는 i를 j로 바꿔야 함을 의미한다.

교화 가능한 부분 계산을 위해서 다음과 같이 정의한다.

for i in range(3):
    for j in range(i + 1, 3):
        tmp = min(wrong[i][j], wrong[j][i])
        num_changes += tmp
        wrong[i][j] -= tmp
        wrong[j][i] -= tmp
        remain = max(wrong[i][j], wrong[j][i])

i ↔ j 끼리 바꿔서 해결 가능한 개수는 min(wrong[i][j], wrong[j][i])이다.

이걸로 교환하고 남은 애들은 사이클로 해결해야 하기 때문이다.

위에서 말한 사이클은 다음과 같다.

num_changes += 2 * remain

예를 들어서 1→ 2, 2→ 3, 3 → 1과 같이 순환하는 경우는 2번 바꿔야 한다.

다 끝났다면 최소 교환 횟수를 저장한다.

answer = min(answer, num_changes)

코드

# 백준 2450 - 모양 정돈
# 분류 : 브루트포스

from itertools import permutations

N = int(input())
A = list(map(int, input().split()))
A = [x - 1 for x in A]

answer = 1e9
count = [0] * 3
for x in A :
    count[x] += 1

for permutation in permutations(range(3), 3) :
    B = []
    for x in permutation :
        B += [x] * count[x]
    
    wrong = [[0] * 3 for _ in range(3)]
    for i in range(N) :
        if A[i] != B[i] :
            wrong[A[i]][B[i]] += 1

    num_changes = 0
    remain = 0

    for i in range(3) :
        for j in range(i + 1, 3) :
            # i -> j, j -> i, a, b min(a, b)
            tmp = min(wrong[i][j], wrong[j][i])
            num_changes += tmp

            wrong[i][j] -= tmp
            wrong[j][i] -= tmp
            remain = max(wrong[i][j], wrong[j][i])

    # i -> j, j -> k, k -> i : 2번, 같은 수,
    num_changes += 2 * remain
    answer = min(answer, num_changes)

print(answer)