문제를 요약하자면, 자신의 양 옆에 친한 학생들만이 존재하도록 원탁에 학생들을 배치할 수 있는 방법을 출력하라는 것이다. 해당 사진에는 나와있지 않지만, 직접 링크를 타고 들어가보면 친한 학생들의 명수에 대한 조건이 주어진다.
19702번: 친구
선린인터넷고등학교에는 $N$명의 학생들이 있다. $N$명의 학생들 가운데 일부는 서로를 좋아한다. 신기한 사실이 있는데, 학생들 간에 일방적으로 좋아하는 경우는 없고, 반드시 서로 좋아하거나
www.acmicpc.net
이 문제는 조합론적으로 어떤 아이디어를 잘 적용해서 풀 수 있는 문제이지만, 본 글에서는 조금 다른 방법을 설명하고자 하는데, 바로 dlas를 사용하는 것이다. dlas같은 경우에는 이전의 squid game을 해결할 때 언급한 알고리즘이며, 역시 본 글에서는 설명하지 않고 dlas를 통한 풀이만을 설명할 것이다.
...라기에는 사실 풀이가 상당히 직관적이라 크게 설명할 것이 없는데, 학생들의 배치를 하나의 상태로 정의한 다음, 어떤 두 학생을 골라 교환하는 작업을 통해 인접한 상태로 전이하는 함수를 만든다. 평가함수는 양 옆에 있는 학생이 전부 친한 학생의 명수이다. 이렇게 dlas를 적용하면 안정적으로 문제를 해결할 수 있다.
'사풀이' 카테고리의 다른 글
| 백준 1557 - 제곱 ㄴㄴ (1) | 2022.12.20 |
|---|---|
| 백준 23575 - Squid Game (1) | 2022.12.20 |
| 백준 7577-탐사 (2) | 2022.12.20 |
