https://www.acmicpc.net/problem/17384
| 시간 제한 | 메모리 제한 |
| 1초(추가 시간 없음) | 1024MB |
문제
수빈이는 예전부터 UCPC의 대회 형식이 ICPC와 같다는 것이 마음에 들지 않았다. 그래서 전대프연의 회장이 되자마자 UCPC를 ICPC와 차별화된 토너먼트 방식의 대회로 바꾸겠다고 선언했다.
수빈이가 바꾼 새로운 UCPC의 진행 방식은 다음과 같다.
- 참가한 팀의 수보다 크거나 같은 가장 작은 2의 거듭제곱 꼴의 수를 찾고, 그 수만큼 빈 슬롯을 일렬로 나열한다.
- 참가한 팀들을 슬롯들에 적절히 배정한다. 이때 두 개 이상의 팀을 같은 슬롯에 배정할 수는 없다.
- 슬롯들을 앞에서부터 두 개씩 짝짓는다. 만약 짝지어진 두 슬롯 모두 팀에 배정되어 있다면 두 팀이 경기를 치르고, 패배한 팀의 슬롯이 삭제된다. 그렇지 않다면 경기를 치르지 않고, 비어있는 슬롯 하나가 삭제된다.
- 마지막 한 팀이 남을 때까지 3번 과정을 반복한다. 마지막으로 남은 팀이 우승팀이 된다.
수빈이는 팀을 배정할 때 가장 앞의 슬롯부터 차례대로 한 팀씩 배정하려고 했으나, 이러면 공평하지 않은 대진표가 만들어진다는 것을 발견했다. 예를 들어 5개의 팀이 대회에 참가했을 때, 첫 번째 슬롯에 배정된 팀은 우승하기 위해 세 번의 경기를 치러야 하지만 5번째 슬롯에 배정된 팀은 한 경기만 치르면 우승을 차지할 수 있다.
수빈이는 우승하기 위해 가장 많은 경기를 치러야 하는 팀과 가장 적은 경기를 치러야 하는 팀의 경기 수가 많아야 한 경기 차이가 나도록 팀을 배정하려고 한다. 또한, 그런 배치가 여러 개 있다면 팀이 배정된 슬롯들의 번호를 내림차순으로 정렬했을 때 이 수열이 사전 순으로 가장 앞서는 배치를 고르려고 한다. 즉 마지막 팀이 배정된 슬롯의 번호가 작을수록 좋은 배치이다.
그러나 대회를 열기 위해서는 대진표를 짜는 것 외에도 할 일이 너무나도 많다! UCPC가 원활히 진행될 수 있도록 바쁜 수빈이 대신 좋은 대진표를 만들어 주자.
입력
첫 줄에 대회에 참가한 팀의 수를 의미하는 정수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫 줄에 수빈이가 원하는 대로 팀을 배정한 결과를 나타내는 문자열을 출력한다. 문자열의 길이는 슬롯의 개수와 같아야 하며, 팀이 배정된 슬롯은 #, 비어 있는 슬롯은 . 으로 나타낸다.
풀이
저는 이런 문제 만나면 일단 작은 수부터 차례로 출력을 만들어가며 규칙을 찾아봅니다. N의 범위는 1부터 시작됩니다.
'''
1 = #
2 = ##
3 = ###.
4 = ####
5 = ###.##..
6 = ######..
7 = #######.
8 = ########
9 = ###.##..####....
10 = ######..####....
11 = #######.####....
12 = ############....
13 = ###########.##..
14 = ###########.###.
15 = ###############.
16 = ################
'''우선 여기까지만 만들어놓고 봅시다. 처음엔 문제를 잘못 이해해서 이 출력도 잘못만들어 여러 번 틀렸는데 문제의 조건에 따르면 이렇게 만드는 게 맞습니다. 예를 들어 처음엔 6을 "###.###."로 만들어야 하는 줄 알았으나 사전 순으로 더 빠르고 문제 조건에 맞는 대진표는 "######.."입니다.
잘못 생각했던 규칙은 이렇습니다. n으로 대진표를 만들 때 k, k+1 또는 k, k로 나누어 대진표를 만드는 겁니다. 그래서 12는 6, 6으로, 6은 다시 3, 3으로, 3은 다시 2, 1로 나누어 만들었는데 이렇게 만드는 게 아닙니다. 위에 만들어진 출력에서 규칙을 살펴봅시다.
각 대진표 오른쪽에 있는 a/b는 그 대진표가 같은 길이의 부분 대진표로 나누어지며 양쪽에 배치된 팀의 수가 a, b라는 의미입니다.
'''
1 = # = 분할 되지 않음(기본 단위)
2 = # / # = 1/1
3 = ## / #. = 2/1
4 = ## / ## = 2/2
5 = ###. / ##.. = 3/2
6 = #### / ##.. = 4/2
7 = #### / ###. = 4/3
8 = #### / #### = 4/4
9 = ###.##.. / ####.... = 5/4
10 = ######.. / ####.... = 6/4
11 = #######. / ####.... = 7/4
12 = ######## / ####.... = 8/4
13 = ######## / ###.##.. = 8/5
14 = ######## / ###.###. = 8/6
15 = ######## / #######. = 8/7
16 = ######## / ######## = 8/8
'''뭔가 규칙이 보이는 것 같습니다. a/b는 a가 먼저 1씩 늘어나고 b가 따라서 1씩 늘어난 후에 a와 b가 모두 n의 절반에 도달하면 다음 단계로 넘어갑니다. 다음 단계에서는 다시 a가 1씩 늘어나는 식입니다. a와 b가 늘어나는 구간은 n이 2^k보다 클 때, 2^(k-1)에서 시작해 2^k까지 입니다.
따라서 다음 값인 17을 예상해보면 17은 2^4보다 큽니다. 따라서 a와 b는 8로 시작해 16까지 증가할 겁니다. 16에서 넘어온 첫 숫자이므로 8/8에서 a가 1 증가한 9/8입니다. 그리고 9는 "###.##..####....", 8은 "########"로 이미 생성되어있습니다. 이 둘을 이어보면 "###.##..####.... / ########"가 됩니다. 대진표의 길이가 2의 거듭제곱꼴이 아니므로 남은 8칸은 모두 .으로 채워주면 "###.##..####.... / ########........"가 완성됩니다.
이 규칙에 따라 1부터 순차적으로 다음 값을 생성해 나가면 누적적으로 n의 대진표를 만들 수 있습니다. 하지만 n이 1,000,000까지이므로 매우 오랜 시간이 걸립니다. 실제로 1부터 순차 생성하는 코드를 작성하면 10,000을 입력해도 생성에 꽤 긴 시간이 걸립니다.
잘 생각해보면 n의 대진표를 만들 때 1부터 n - 1까지 모든 대진표가 다 필요하지 않습니다. 만약 1752의 대진표를 만든다면 다음 대진표만 필요합니다.
1752 = 1024 / 728
1024 = # * 1024
728 = 472 / 256
256 = # * 256
472 = 256 / 216
216 = 128 / 88
128 = # * 128
88 = 56 / 32
32 = # * 32
56 = 32 / 24
24 = 16 / 8
16 = # * 16
8 = # * 8
이렇게 분할 정복으로 이어붙여 나가면 O(logN)에 문제를 해결할 수 있습니다. 한 번 찾은 값은 dictionary에 저장해놓고 계속 불러오도록 합니다.
정답 코드
import sys
input = sys.stdin.readline
write = sys.stdout.write
def solution():
n = int(input())
memo = [''] * (n + 1)
memo[1] = "#"
def dq(k):
if k == 1: return '#'
if memo[k]: return memo[k]
b = 1
while b < k: b <<= 1
d = (b * 3) // 4
b >>= 1
if k > d:
memo[b] = dq(b)
memo[k - b] = dq(k - b)
return memo[b] + memo[k - b]
else:
b >>= 1
memo[k - b] = dq(k - b)
memo[b] = dq(b)
return memo[k - b] + memo[b] + '.' * b
write(dq(n))
solution()
