[코드포스] Codeforces Round #636 (Div. 3)

대회 링크: http://codeforces.com/contest/1343

A번 문제: http://codeforces.com/contest/1343/problem/A

 

  정수 n이 주어졌을 때, 정수 k가 1보다 큰 조건 하에서 다음을 만족시키는 양수 x가 하나라도 있는지 찾는 문제다.

 

 

[ 문제 해설 ]

 

  이 문제는 완전 탐색(Brute Forcing)으로 해결할 수 있다. k를 2부터 쭉 증가시켜보자. n은 다음과 같이 표현된다.

 

  3x = n

  7x = n

  15x = n

  31x = n

  63x = n

  ...

 

  보면 x의 계수가 기하급수적으로 증가한다. 이 때 n은 최대 1,000,000,000이기 때문에, 모든 경우의 수를 고려해도 빠르게 문제를 풀 수 있다. (대략 k가 30만 되어도 계수는 10억에 근접할 것이다.)

 

  그래서 3x, 7x, 15x, 31x, 63x, ... 이렇게 증가 시키면서, n이 각 계수로 나누어 떨어지는지 확인한다. 만약 나누어 떨어진다면 그 때의 x를 출력하면 정답이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    coefficient = 2
    now = 3 # now는 3, 7, 15, 31, ...와 같이 증가한다.
    while True:
        # n이 now로 나누어 떨어진다면
        if n % now == 0:
            # 그 몫을 출력한다.
            print(n // now)
            break
        coefficient *= 2
        now += coefficient

 

B번 문제: http://codeforces.com/contest/1343/problem/B

 

  배열의 크기 n이 주어졌을 때, 이 배열의 앞 부분 절반은 짝수 원소로만 구성되고, 뒷 부분 절반은 홀수 원소로만 구성된다고 한다. 이 때 모든 원소들은 서로 다르다. 앞 부분의 합과 뒷 부분의 합이 동일하게 되는 리스트를 하나라도 찾으면 되는 문제다.

 

  예를 들어 N = 4일 때, 2 4 1 5를 찾으면 정답이다. N = 8일 때는 2 4 6 8 1 3 5 11를 찾으면 정답이다.

 

[ 문제 해설 ]

 

  이 문제는 홀수 합의 특징을 생각하면 어렵지 않게 풀 수 있다. 홀수를 홀수 번 더하면 홀수이다. 즉, N / 2가 홀수라면 리스트를 만들 수 없다. 예를 들어 N = 6 이라면, 리스트를 만들 수 없다. 즉 N이 4의 배수일 때만 리스트를 만들 수 있다. 그렇다면 N이 4의 배수일 때는 리스트를 어떻게 만들면 될까?

 

  앞 부분 절반은 그냥 2부터 하나씩 나열한다. 뒷 부분 절반은 앞 부분에서 1씩 더하거나 빼서 만들 수 있다. (정확히는 뒷 부분 절반의 합이 앞 부분 절반의 합이 되어야 하므로, 뒷 부분 절반을 또 절반으로 나누어서 처리하면 된다.)

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    # N이 4의 배수일 때 리스트를 만들 수 있다.
    if n % 4 != 0:
        print("NO")
    else:
        print("YES")
        front = []
        # 앞 부분 절반(짝수 부분)은 2부터 하나씩 출력
        for i in range(1, n // 2 + 1):
            print(i * 2, end=' ')
            front.append(i * 2)
        # 뒷 부분 절반(홀수 부분)의 절반은 -1씩 해서 출력
        for i in range(n // 4):
            print(front[i] - 1, end=' ')
        # 뒷 부분 절반(홀수 부분)의 남은 절반은 +1씩 해서 출력
        for i in range(n // 4, n // 2):
            print(front[i] + 1, end=' ')
        print()

 

C번 문제: http://codeforces.com/contest/1343/problem/C

 

  리스트가 주어졌을 때, 리스트의 원소를 앞에서부터 하나씩 확인하며 원소를 고른다. 단, 양수와 음수를 번갈아 가면서 원소를 하나씩 골라야 한다. 처음에 양수를 골랐으면, 다음 번에는 음수를 골라야 한다. 반대로 처음에 음수를 골랐으면, 다음 번에는 양수를 골라야 한다.

 

  이 때, 원소들을 골라서 만들어지는 가장 긴 부분수열 중에서 원소의 합이 가장 큰 것을 찾는 것이 요구사항이다.

 

  예를 들어 수열이 [-2, 8, 3, 8, -4, -15, 5, -2, -3, 1]이라면, 정답 부분수열은 [-2, 8, -4, 5, -2, 1]이 된다. 이 부분 수열의 합은 6이다.

 

[ 문제 해설 ]

 

  이 문제는 같은 부호를 가지는 데이터들을 묶어서 해결할 수 있다. 예를 들어 [-2, 8, 3, 8, -4, -15, 5, -2, -3, 1]라는 수열이 있다면, 이를 다음과 같이 인접한 원소끼리 묶도록 한다.

 

  [-2, 8, 3, 8, -4, -15, 5, -2, -3, 1]

 

  이 때, 같은 묶음 중에서 가장 큰 수를 각각 뽑으면 된다. 이 때 합은 6이 된다.

 

  [-2, 8, -4, 5, -2, 1]

 

  이를 코드로 옮기면 정답이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    result = 0

    # 시작점이 양수인지 음수인지 기록(양수: 1, 음수: -1)
    if data[0] > 0:
        sign = 1
    else:
        sign = -1
  
    # 같은 부호들을 담을 리스트
    array = []
 
    # 리스트의 원소를 하나씩 확인하며
    for x in data:
        # 현재 양수일 때 양수가 나온 경우
        if sign == 1 and x > 0:
            # 같은 부호이므로 담기
            array.append(x)
        # 현재 양수일 때 음수가 나온 경우
        if sign == 1 and x < 0:
            # 현재 부호를 음수로 변환
            sign = -1
            result += max(array)
            array = [x]
        # 현재 음수일 때 음수가 나온 경우
        if sign == -1 and x < 0:
            # 같은 부호이므로 담기
            array.append(x)
        # 현재 음수일 때 양수가 나온 경우
        if sign == -1 and x > 0:
            # 현재 부호를 양수로 변환
            sign = 1
            result += max(array)
            array = [x]
  
    result += max(array)
    print(result)

 

D번 문제: http://codeforces.com/contest/1343/problem/D

 

  길이가 n인 수열이 주어진다. (n은 짝수) 이 수열의 모든 원소는 k 이하의 값을 가진다.

 

  이 때 대칭되는 원소들의 합을 모두 x로 만들고자 한다. 이를 위해 원소를 하나씩 골라서 그 원소의 값을 k 이하의 수로 바꾸는 연산을 수행할 수 있다. 결과적으로 최소 연산의 횟수를 출력하면 되는 문제이다.

 

  예를 들어 [1, 2, 1, 2]의 경우 대칭되는 원소의 합이 각각 3, 3이다. 따라서 x = 3으로 설정했을 때, 연산이 필요하지 않다. 따라서 최소 연산 횟수는 0이다.

 

  또한 [1, 2, 2, 1]의 경우 대칭되는 원소의 합이 각각 4, 2이다. 따라서 x = 4으로 설정했을 때, 첫 번째 원소를 3으로 변경하면 된다. 최소 연산 횟수는 1이다.

 

  또한 [6, 1, 1, 7, 6, 3, 4, 6]의 경우 대칭되는 원소의 합이 각각 13, 4, 5, 12이다. 따라서 x = 8로 설정했을 때, 최소 연산 횟수로 4가 나올 수 있다.

 

[ 문제 해설 ]

 

  이 문제는 아이디어만 잘 떠올리면 쉽게 해결할 수 있는 문제다. 일단 각 대칭 쌍마다 하나의 원소를 변경할 수 있다고 가정해보자. 예를 들어 3번째 예제를 가지고 생각해보자.

 

  [6, 1, 1, 7, 6, 3, 4, 6]를 확인하면, 각 대칭 쌍을 정렬하여 나열하면 다음과 같다. 총 네 개의 쌍이 존재한다.

 

  (1, 3): 합 = 4

  (1, 4): 합 = 5

  (6, 6): 합 = 12

  (6, 7): 합 = 13

 

  이 때 각 대칭 쌍의 원소 중 하나의 값을 변경할 수 있을 때의 범위는 다음과 같다.

 

  (1, 3) → [2, 10]

  (1, 4) → [2, 11]

  (6, 6) → [7, 13]

  (6, 7) → [7, 14]

 

  결과적으로 모든 쌍들의 [lower_bound, upper_bound] 범위를 고려해보자. x를 2부터 2 * n까지 증가시키면서 확인한다고 생각해보자. x = 2라고 하면 (1, 3)과 (1, 4)의 범위에 포함되어 있으므로, 이들은 원소를 1개씩만 바꾸면 된다. 나머지 두 쌍은 원소를 2개 모두 바꾸어야 한다. 즉, x = 2일 때 최소 연산 횟수는 6이 될 것이다. 만약에 x = 7이라면 어떨까? 모든 대칭 쌍이 원소를 1개씩만 바꾸면 된다. 이 때 최소 연산 횟수는 4가 된다. 따라서 x를 증가 시키면서 매 x에 대하여 lower_bound와 upper_bound를 고려해주면 된다.

 

  사실 [2, 2 * n] 범위에 대해서 x를 모두 고려할 필요는 없다. 각 대칭 쌍에 대하여 ① 대칭 쌍의 합, ② lower_bound, ③ upper_bound 세 가지에 대해서만 고려하면 된다. 이들을 포인트(points)라고 하겠다. 포인트는 오름차순 정렬이 되어 있어야 한다.

 

  결과적으로 포인트를 하나씩 확인할 것이다. 이를 위해 lower_bound의 개수를 in_map에 기록하고, upper_bound의 개수를 out_map에 기록한다. 또한 대칭 쌍의 합은 sum_map에 기록하도록 하자. 이제 최소 연산 횟수를 구할 수 있다.

 

points	2	4	5	7	10	11	12	13	14
in_map	2			2
out_map					1	1		1	1
sum_map		1	1				1	1
연산 횟수	6	5	5	4	4	5	5	5	7

 

  결과적으로 최소 연산 횟수는 4가 되는 것이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, k = map(int, input().split())
    data = list(map(int, input().split()))
  
    # 3개의 해시 맵(Hash Map)을 사용합니다.
    in_map = {}
    out_map = {}
    sum_map = {}

    # x의 값으로 확인해야 할 포인트들
    points = set()
 
    for i in range(n // 2):
        min_value = min(data[i], data[n - i - 1])
        max_value = max(data[i], data[n - i - 1])

        # lower_bound, upper_bound, 대칭 쌍의 합 계산
        lower_bound = min_value + 1
        upper_bound = max_value + k
        sum_value = min_value + max_value

        # 모든 lower_bound를 in_map에 기록합니다.
        if lower_bound in in_map:
            in_map[lower_bound] += 1
        else:
            in_map[lower_bound] = 1

        # 모든 upper_bound를 out_map에 기록합니다.
        if upper_bound in out_map:
            out_map[upper_bound] += 1
        else:
            out_map[upper_bound] = 1

        # 모든 대칭 쌍의 합을 sum_map 기록합니다.
        if sum_value in sum_map:
            sum_map[sum_value] += 1
        else:
            sum_map[sum_value] = 1

        points.add(lower_bound)
        points.add(upper_bound)
        points.add(sum_value)
  
    points = sorted(points)
 
    now_sum = 0
    result = n
  
    for i in points:
        # lower_bound의 개수만큼 더하기
        in_count = 0
        if i in in_map:
            in_count = in_map[i]
        now_sum += in_count

        # sum의 개수 구하기
        sum_count = 0
        if i in sum_map:
            sum_count = sum_map[i]

        # 최소 연산 횟수 계산
        now_total = n - (now_sum + sum_count)
        result = min(result, now_total)

        # upper_bound의 개수만큼 빼기
        out_count = 0
        if i in out_map:
            out_count = out_map[i]
        now_sum -= out_count
    
    print(result)