백준 2450. 모양 정돈

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

2450번: 모양 정돈

 

 

문제는 다음과 같은 입력이 주어지면 

8
1 3 3 2 1 1 3 2

위 8개의 숫자들을 연속되도록 만들기 위해 두 개의 숫자의 자리를 바꾸는 연산의 최소 횟수를 구하는 것이다. 

 

생각해보면 모양은 총 3개 있기 때문에 다음 여섯가지 경우 중 하나가 된다.

 

1 1 1 2 2 3 3 3

1 1 1 3 3 3 2 2

2 2 1 1 1 3 3 3

2 2 3 3 3 1 1 1

3 3 3 1 1 1 2 2

3 3 3 2 2 1 1 1

 

그리고 숫자들을 세 개의 영역으로 나눌수 있다.

1이 있어야 하는 영역, 2가 있어야 하는 영역, 3이 있어야 하는 영역이다.

 

[1 1 1 2 2 3 3 3] 을 우선 생각해보자.

원래 수열은 [1 3 3 2 1 1 3 2]이기 때문에 다음과 같이 나타낼수 있다.

[1 1 1 /  2 2 / 3 3 3]  // 목표 

[1 3 3 /  2 1 / 1 3 2]  // 기존 

 

	1	2	3
1	1	0	2
2	1	1	0
3	1	1	1

a[i][j] = i 영역에 있는 j의 갯수다 

즉 a[1][3] = 2 는 1의 영역에 숫자 3이 2개 있다는 의미다. 

 

이렇게 2차원 배열로 만들면 우리의 최종 목표는 배열이 다음과 같아지는 경우라는것을 알 수 있다. 

	1	2	3
1	3	0	0
2	0	2	0
3	0	0	3

배열이 위와같이 나타난 다는 것은 각 영역에 맞는 숫자들이 모였다는 것이고, 수열이 문제의 조건인 연속된 수들로 만들어진 것이다. 

 

---

 

이제 어떻게 위와 같이 만드느냐가 문제인데 위의 2차원 배열을 다시 보자.

	1	2	3
1	1	0	2
2	1	1	0
3	1	1	1

1 행은 1의 영역을 나타내는데 지금 보면 1의 영역에 숫자 3이 2개 있다.

우리는 최소 횟수로 문제의 조건을 만족하고 싶기 때문에 가장 베스트인 경우는 1의 영역에 있는 3과, 3의 영역에 있는 1의 자리를 바꾸는 것

이다. 

 

3의 영역의 1은 a[3][1] = 1 이므로 1개 존재한다. 

따라서 a[1][3]과 a[3][1]을 1씩 빼주고, 각각의 영역에 서로 맞바꾼 숫자의 수를 증가시켜주면 된다. 

	1	2	3
1	2	0	1
2	1	1	0
3	0	1	2

 

하지만 아직 1의 영역에 3이 1개 남았다.

그러면 이제 2의 영역에서 바꿔주면 된다.

2의 영역에 1 즉 a[2][1] = 1이기 때문에 바꿔줄수 있다.

 

	1	2	3
1	3	0	0
2	0	1	1
3	0	1	2

 

이제 배열을 보면 2의 영역에 3이 있다.

3의 영역에 2가 하나 있으므로 바꿔줄수 있다.

 

	1	2	3
1	3	0	0
2	0	2	0
3	0	0	3

이렇게 하면 목표 배열이 완성 됐고 총 3개의 숫자 자리가 바뀌었다.

 

---

위에서 말한 여섯가지의 조합에 대하여 위 연산을 수행하고 최솟값이 정답이다.