[코드포스] Codeforces Round #669 (Div. 2)

대회 링크: codeforces.com/contest/1407

A번 문제: codeforces.com/contest/1407/problem/A

 

  이 문제는 0 혹은 1로만 구성된 수열이 주어졌을 때, 순서를 유지한 상태로 최대 N / 2개의 원소를 삭제해서 다음의 식이 성립하도록 만들어야 한다. (N은 항상 2의 배수)

 

  a1 - a2 + a3 - a4 + ... = 0

 

[ 문제 해설 ]

 

  이 문제의 해결 아이디어는 꽤 간단하다. 먼저 수열에 들어 있는 0과 1의 개수를 각각 계산한다.

 

  ① 만약 0의 개수가 더 많거나 같다면 0의 개수만큼 출력하면 된다. ② 만약 1의 개수가 더 많다면 1의 개수만큼 출력해야 한다. 단, 1의 개수가 홀수인 경우에는 1개 적은 만큼 출력해야 한다.

 

  예를 들어 [1, 0, 1, 0, 0, 0]이 들어왔을 때에는 [0, 0, 0, 0]을 출력하면 된다. [1, 0, 1, 1, 1, 0]이 들어왔을 때에는 [1, 1, 1, 1]을 출력하면 된다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    zero = 0
    one = 0
    for x in data:
        if x == 0:
            zero += 1
        else:
            one += 1
    if zero >= one:
        print(zero)
        for i in range(zero):
            print(0, end=' ')
    else:
        print(one // 2 * 2) # 홀수인 경우 1이 더 작은 수를 이용
        for i in range(one // 2 * 2):
            print(1, end=' ')
    print()

 

B번 문제: codeforces.com/contest/1407/problem/B

  이 문제는 N개의 양의 정수를 담은 수열 a1, a2, a3, ..., an이 있을 때, 원소를 하나씩만 사용해서 수열 b1, b2, b3, ..., bn를 만드는 문제다. 이때 ci = GCD(b1, ..., bi)라고 하자. 우리는 수열 c1, c2, c3, ..., cn이 사전적으로 최댓값을 가지도록 하고 싶다.

 

  예를 들어 수열 A = {64, 25, 75, 100, 50}라고 하면, 정답 수열 B = {100, 50, 25, 75, 64}를 찾을 수 있다.

 

[ 문제 해설 ]

 

  이 문제는 완전 탐색으로 해결할 수 있다. 그냥 이중 반복문을 돌리면서 Maximum을 찾으면 된다. 다만, GCD(x, y, z) = GCD(GCD(x, y), z)라는 점을 알고 있어야 한다. 또한 0은 모든 정수의 배수라는 점에서 GCD(0, x) = x라는 점을 기억하자. 사실 이는 잘 알려진 공식이므로 이를 이용하여 쉽게 문제를 해결할 수 있다. 참고로 GCD 함수는 로그 복잡도를 가지므로 빠르게 동작한다.

 

[ 정답 코드 ]

 

import math
 
for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    gcd_value = 0
    for i in range(n):
        max_value = (0, 0) # (현재 GCD 값, index)를 한꺼번에 묶어서 저장
        for j in range(n):
            if data[j] != -1: # 아직 출력하지 않은 데이터 중에 GCD 값을 가장 크게 만드는 데이터 찾기
                max_value = max(max_value, (math.gcd(gcd_value, data[j]), j))
        gcd_value = max_value[0] # GCD 값 갱신
        print(data[max_value[1]], end=' ') # 해당 데이터 출력
        data[max_value[1]] = -1 # 해당 데이터 처리 완료
    print()

 

C번 문제: codeforces.com/contest/1407/problem/C

  이 문제는 1부터 N까지의 값을 하나씩 가지고 있는 하나의 순열(Permutation)을 찾는 문제다. 우리는 최대 2 * N만큼의 쿼리를 날려서 정보를 얻어올 수 있다.

 

  이때 ? i j라고 쿼리를 날리면, pi mod pj의 값을 알려준다.

 

[ 문제 해설 ]

 

  나도 이 문제를 풀면서 떠올리게 된 사실인데, 두 양의 정수가 있을 때 쿼리를 두 번 날리면 누가 더 큰 지를 알 수 있다. 예를 들어 서로 다른 양의 정수 x와 y가 있을 때 다음의 명제가 성립한다.

 

  x mod y > y mod x라면, ① x보다 y가 더 크며 ② x mod y = x이다.

 

  따라서 앞에서부터 두 수씩 묶어서 쿼리를 날려 본다. 쿼리를 날리면서 항상 몇 번째 수가 가장 큰 지를 저장하면서, 우리는 더 작은 수의 값을 매번 확실히 찾을 수 있다.

 

import sys
 
n = int(input())
 
answers = [-1] * (n + 1)
 
max_index = 1
next_index = 2
 
for i in range(n - 1):
    print("?", max_index, next_index)
    sys.stdout.flush()
    one = int(input())
    print("?", next_index, max_index)
    sys.stdout.flush()
    two = int(input())
    if one < two:
        answers[next_index] = two
    else:
        answers[max_index] = one
        max_index = next_index
    next_index += 1
 
answers[max_index] = n
 
print("!", end=' ')
for i in range(1, n + 1):
    print(answers[i], end=' ')