BOJ 2450번: 모양 정돈

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

2450번: 모양 정돈

어렵다..

세가지 모양이 있고 각 모양이 적어도 하나 이상 나타나기 때문에 가능한 순서는 3! = 6가지 경우가 있다.

따라서 이 6가지 경우를 모두 보면서 각각의 이동횟수 중 최소를 출력하면 된다.

 

이동횟수를 구하는 방법은 더 어려웠다.. 검색해보니 대충 이해가 될 듯 한데 명확히 왜 그게 맞는지를 설명을 못하겠다. 어렴풋이 이해가 되는 정도..? 그냥 아예 확 외워버리는 게 나을수도 있겠다,,

 

import sys
from itertools import permutations
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
cnt = [0]*4
ans = float('INF')

for i in arr:
    cnt[i]+=1

for n in permutations([1,2,3], 3):
    p = 0
    pos = [[0] * 4 for _ in range(4)]
    for i in range(3):
        for j in range(cnt[n[i]]):
            pos[n[i]][arr[p]] += 1
            p += 1
    ans = min(ans, pos[1][2]+pos[1][3]+max(pos[2][3],pos[3][2]))

print(ans)