짜잘하고 어디 쓸데도 없어보이지만 KOI, swexpertacademy에서 풀어 볼 문제가 있기 때문에 알아두면 좋을 것 같다. bfs, 정렬 등 방법은 많지만 가장 간단한 방법을 소개하려고 한다. 이 방법은 이해만 해두면 구현은 두세줄 정도로 매우 쉽다!
<개요>
빨강, 초록, 파랑 바구니에 여러개의 빨강, 초록, 파랑공이 무작위로 담겨있을 때, 각 공을 색깔에 맞는 바구니에 넣고자 한다. 두 공의 위치를 바꾸는 행동을 최소 몇 번해야 완벽히 정돈될까?
다음과 같은 상황을 생각해보자.
(1) 우선 빨간색 바구니부터 채운다.
빨간 바구니의 초록공은 최대한 초록 바구니의 빨간공과 교환한다.
빨간 바구니의 파란공은 최대한 파란 바구니의 빨간공과 교환한다.
(이 경우엔 빨간 바구니의 초록공이 파란 바구니로 들어갔지만, 다른 경우엔 파란공이 초록 바구니에 들어갈 수도 있다.)
빨간 바구니의 빨간색이 아닌 공의 수 = 초록,파란 바구니의 빨간 공의 수 임을 유념하자.
(2) 나머지 바구니를 정리한다.
<풀이>
빨간색 초록색 파란색 바구니를 각각 0,1,2번 영역, 빨간색 초록색 파란색 공을 0,1,2번 요소라고 하자.
(1)에서 필요한 교환 횟수는 다음과 같다. (둘 중 아무거나 쓰면 됨)
- 0번 영역에 포함된 1,2번요소의 개수
- 1번 영역에 포함된 0번 요소의 개수 + 2번 영역에 포함된 0번 요소의 개수
(2)에서 필요한 교환 횟수는 다음과 같다.
- $max$(2번 영역에 포함된 3번 요소의 개수, 3번 영역에 포함된 2번 요소의 개수)
(2)에서 필요한 교환 횟수를 (1)이 지난 현재 상황에서 파악하는게 쉽지가 않다. 왜냐하면 (1) 과정 후에 상황을 초기 상황에서 정확하게 유추하는 것이 불가능하기 때문이다. (1)설명의 접은 글을 생각해보면 이유를 알 수 있다.
하지만 결국 두 상황 중 하나이므로 다음과 같이 간단하게 구할 수 있다.
위 예시에서, (1)과정에서 빨간 바구니에 포함된 초록색 공이 초록 바구니로 더이상 들어갈 수 없어서 파란색 바구니로 흘러 들어간 것을 볼 수 있다.
우리는 (1)과정 이후에 2영역에서 3번 요소의 개수 혹은 3영역에서 2번 요소의 개수가 필요하다.
초기 초록색 바구니의 파란 공의 개수와, (1) 과정 이후 초록 바구니의 파란 공의 개수가 같다.
초기 파란색 바구니의 초록 공의 개수와, (1) 과정 이후 파란 바구니의 초록 공의 개수는 다르다.
반대로 위 예시가 아닌 빨간 바구니에 포함된 파란 공이 파란 바구니로 더이상 들어갈 수 없어서 초록 바구니로 흘러 들어간 경우가 있을 수 있다.
정리하자면, $arr[i][j]$ : $i$번 영역에 포함된 $j$번 요소의 개수라 하면
전체 정리 회수는
(1) $arr[0][1]+arr[0][2]$ 혹은 $arr[1][0] + arr[2][0]$
(2) $max( arr[1][2], arr[2][1] )$
둘을 합해준 값이 되겠다.
<연습문제1>
swexpertacademy. 로그인 후 링크클릭
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
풀이 : https://suuntree.tistory.com/80
<연습문제2>
KOI 중등부
문제 : https://www.acmicpc.net/problem/2450
2450번: 모양 정돈
첫째 줄에는 모양의 전체 개수 N이 주어진다. N은 3이상 100,000이하이다. 둘째 줄에는 나열된 모양들을 나타내는 N개의 정수가 빈 칸을 사이에 두고 주어지는데, 정수 1은 세모를, 정수 2는 네모를, 정수 3은 동그라미를 나타낸다. 각 모양은 최소 한번 이상 나타난다.
www.acmicpc.net
풀이 : https://suuntree.tistory.com/75?category=797985
<생각>
쓸 수 있는 곳이 매우 한정된 풀이방법이다. 정돈을 못하는 경우도 고려하지 않는다.
구간의 수가 3이 넘어간다면 위 방법을 그대로 적용할 수 없다. 그래도 도움이 될지도?
