[BOJ 24727] 백준 24727번 - 인지융~

		2022 연세대학교 신학기맞이 프로그래밍 경진대회 풀이
A		[BOJ 24723] 녹색거탑
B		[BOJ 24724] 현대모비스와 함께하는 부품 관리
C		[BOJ 24725] 엠비티아이
D		[BOJ 24726] 미적분학 입문하기 2
E		[BOJ 24727] 인지융~
I		[BOJ 24731] XOR-ABC

1. 문제

$24727$. 인지융~ (2022 연세대학교 신학기맞이 프로그래밍 경진대회 E번)

백준 24727번 - 인지융~ (https://www.acmicpc.net/problem/24727)

2. 풀이

$C$개의 $A$와 $E$개의 $B$를 $N\times N$ 공간에 배치하는데, $A$가 전부 연결되고, $B$ 또한 전부 연결되어 있으며, $A$공간과 $B$공간이 연결되어 있지 않게 해야 한다.

이 조건을 만족하면서 모두 배치하기 위해서는 어떠한 최적의 배치 방법이 필요하다. 그 방법은 그림과 같다.

나는 N, C, E 각각의 값을 여러 개 설정하고 직접 최적으로 그려보면서, 규칙을 일반화하려 노력했다. 그리고 해당 방법을 찾아낼 수 있었다.

아니면, 다음과 같은 근거를 통해 해당 방법을 도출해낼 수도 있다.

하나의 $1\times 1$ 공간에 맞닿는 변은 총 네 개이고, $A$를 기준으로 $B$와 연결되지 않으면서 최대한 많은 개수를 사용하려면, 맞닿는 변이 공간 밖이거나 $A$여야 한다.
이를 만족하면도록 $A$를 채워나가면 그림과 된다. 그 이후 $B$를 채울 때도 마찬가지이다.

$C$개의 $A$를 그림과 같은 방식으로 먼저 다 채운 후, $B$를 그림과 같은 방식으로 점차적으로 채우면서, $A$와 맞닿는 일이 생기면 -1을 출력하도록 했다.

3. 채점 결과

4. 회고

최적의 방법을 떠올리는 것도 쉽지 않았고, 그 방법을 코딩하는 것도 만만치 않은 문제였다. 대각선 탐색은 여전히 까다롭다.

5. 코드