[백준 16438번] 원숭이 스포츠

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/16438

16438번: 원숭이 스포츠

 

백준 16438번 문제 원숭이 스포츠

문제의 설명이 조금 어려운데, 요약하면 다음과 같습니다.

N개의 원소에 대해, 총 7번의 기회 이내에 배열 내의 원소 i가 원소 j (i != j)와 다른 경우가 적어도 한 번 이상 존재해야 합니다.

 

문제의 조건을 유심히 살펴보고 분석해 보면 다음과 같은 사실을 알 수 있습니다.

N은 최대 99인데, 주어진 주는 7주입니다.

전체 원숭이를 재귀적으로 반씩 나누어 팀을 할당하는 방법을 생각해 보면, 2^7 = 128이므로 N은 7번 이내에 무조건 모든 원숭이들이 각자 다른 팀이 되도록 할 수 있습니다.

 

그러면 앞서 말한대로, 전체 원숭이를 반으로 나누고, 두 그룹을 각자 다른 팀에 할당하는 과정을 합니다.

이후, 각 그룹에 대해, 위 과정을 반복합니다. 즉, 각 그룹을 반으로 나누어 팀 A와 B에 할당합니다.

따라서 이는 재귀로 구현할 수 있습니다. 분할 정복 (divide and conquer) 방법으로 접근하는 것입니다.

 

n = 7인 경우 (문제에서 주어진 예시), 2^3 = 8이 n보다 큰 가장 작은 2의 제곱수 입니다. 따라서 위 과정을 3번 반복하면 모든 경우의 수를 얻을 수 있습니다.

하지만 문제에서는 총 7줄의 답을 출력하는 것을 요구하므로, 이에 대한 처리를 해야 합니다.

앞에서 문제의 조건은 다 갖추었으므로, 저는 남은 줄을 모든 원숭이들이 한 마리만 빼고 전부 A팀에 속하는 경우를 출력하였습니다.

 

배열의 빈 곳이 있는 경우 확인하고 홀수인 경우 A, 짝수인 경우 B를 넣고 출력해 주었습니다.

 

채점 결과

예외 처리 (N < 7인 경우), 버그 잡기 등 때문에 몇 번 틀리고 나서 맞았네요.