문제 링크
https://www.acmicpc.net/problem/16438
🛠️ 미해결
- 풀이시간 : 1시간 50분
- 분할정복에서 주는 깊이와 횟수와의 연관성모름 : 날짜를 7일로 주는 것에서 특별한 의미를 찾지 못하였다. 알고보니 100개의 팀을 나누어 들어가는데 있어서 대략 정도의 횟수가 소진 되므로 나누어 들어가는 것이였다... 여기서부터가 힌트였다니...
- 아이디어를 생각하지 못함 : 해답을 보고도 처음에 왜 이게 되지라는 생각을 하였다. 왼쪽과 오른쪽으로 나누면 왼쪽과 오른쪽 팀원들은 한번 다른 팀을 해보았고 이를 단계별로 나눠들어가는게 아이디어였다. 모든 다른 원숭이와 한번 이상씩 다른 팀을 해야한다는 조건사항에서 분할정복을 떠올리지도 못하였고 이러한 아이디어에 접근하지도 못하였다. 왜 떠올리지 못하였을까? 쌍을 이루려고 하였다. 즉 모든 원숭이끼리의 경기이력이 필요하다고 생각하였고 이 생각을 팀 단위로 생각하지 못하였다. 왜 여기서 팀단위로 생각하지 못하였는가? 7일이라는 조건에서 규칙성이 없다고 생각하였다. 즉, 이게 나누는 깊이라고 생각하지 않고 분할을 하였을 때, 돌아오는게 없다고 생각했다. 즉 생각하지 못한 이유는 팀을 이루기 위해서는 개개인을 따져야 한다고만 생각했다. 이걸 고려해서 다음 단계를 따져야한다고 생각하였다. 왜 개개인만 따졌을까? 팀을 이분할 하였을 때, 한쪽 팀을 이미 상대했다면 남은 팀안에서만 나눌 생각을 하지 못하였다. 이미 상대한 쪽은 냅두고 다른 상대에서 상대하는 방법을 생각하긴 했다. 하지만 이것을 전체적인 구조로 보지 못하였다. 단계를 나누는데 있어서 전에 상대해본 사람들이 이후의 결과에 영향을 준다고 생각하였기에 개개인으로 결과를 따졌다. 왜 그랬나? 팀을 일일이 구성하려고 하였기 때문이다. 왜? 팀을 구성하는데 있어서 한꺼번에 만드는 방법을 생각해본 경험이 적기도 하고, 정답 예제를 보고 팀을 한꺼번에 만드는것이 아니라 한꺼번에 만들 수 없다고 생각했기 때문이다. 즉, 경험 부족과 정답 예제를 가지고 답을 추론하는 잘못된 접근 방식 때문이다. 또한 팀을 구성할 때, 하나씩 잡고 팀을 구성하려는 습관 때문이다. 어떤 기준을 적용하는데 있어서 기준으로 한명씩 잡고 팀을 구성하려고 한다. 서로 다른 분류로 들어갈 때에는 전체적으로 그 분류에 따라 나눌 수 없는가를 생각해보려고 해야한다.
🕒 Python 풀이시간: x
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
cur = ['A'] * n
ans = set()
def dq():
q = deque([(0, n)])
while q:
for _ in range(len(q)):
start, end = q.popleft()
if end - start <= 1:
continue
mid = (start + end) // 2
for i in range(start, mid):
cur[i] = 'A'
for i in range(mid, end):
cur[i] = 'B'
q.append((start, mid))
q.append((mid, end))
ans.add(''.join(cur))
dq()
for a in ans:
print(a)
for _ in range(7 - len(ans)):
print('A' + ('B' * (n - 1)))원숭이 팀 구성: 서로 다른 팀으로 나누기! 🐒🏆
원숭이가 스포츠 팀을 만드는데 있어서 서로 다른 원숭이들 끼리는 서로 한번 이상 씩은 다른 팀에 속해야 하는 문제이다. 팀을 나누는데 중점을 두어야 한다.
한번씩 다른 팀에 속해야 하므로 다른 팀으로 나누는 방법을 생각해볼 수 있다. 즉, 팀을 구성하는 첫번째 방법은 반으로 쪼개서 생각하는 것이다. 이러한 접근을 하였다면 이제 그 나눈 팀 안에서만 팀원 들과 다른 팀을 맺어보면 된다는 생각으로 들어가야 한다. 즉, 분할 정복인 것이다. 그 과정이 N이 100개 일 때 7일이면 128가지가 나올 수 있기 때문에 7일 내로 모든 가짓수가 가능하다는 점도 분할 정복을 이렇게 사용한다는 이론에 날개를 달아준다.
이렇게까지 생각을 하였다면 이제 이론을 적용시켜 구현하면 된다. 각 범위에 따라 나눈 단계를 나누어야 하므로 범위를 담고 다음 범위를 전부 담아가면 된다. 즉, 나눈 범위에 층을 나누어서 진행한다. 풀이에서는 큐를 통해 한번 단계를 전부 큐에 담고 그 큐를 비울 때까지 진행하는 식으로 범위가 나눠지는 단계를 나누었다.
이렇게 Python으로 백준의 "원숭이 스포츠" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
