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

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

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

 

  N개의 수가 있다. 예를 들어 N = 8이라고 하면, 다음과 같이 수가 나열된다.

 

  원래 배열: a1, a2, a3, a4, a5, a6, a7, a8

 

  이때 다음과 같은 규칙에 따라 수를 재나열한다.

 

  변경된 배열: a1, a3, a5, a7, a8, a6, a4, a2

 

  이 문제에서의 요구사항은, 변경된 배열을 보고 원래의 배열을 맞추는 것이다. 문제 해결 아이디어는 굉장히 심플하다. 앞에서부터, 그리고 뒤에서부터 번갈아 가면서 출력하면 된다.

 

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    for i in range(n): 
        if i % 2 == 1:
            print(a[n - (i // 2) - 1], end=' ')
        else:
            print(a[i // 2],end=' ')
    print()

 

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

 

  문장이 주어졌을 때, 하나의 substring을 제거하여 "2020"이라는 문자열을 만들 수 있는지 체크하는 문제다. 이 문제를 풀기 위한 가장 간단한 방법은 제일 앞부분과 제일뒷 부분을 확인하여 "2020"을 만들 수 있는지 확인하는 것이다.

 

앞	뒤
(공백)	2020
2	020
20	20
202	0
2020	(공백)

 

for _ in range(int(input())):
    n = int(input())
    data = input()
    
    if data[n - 4:] == "2020":
        print("YES")
    elif data[:1] == "2" and data[n - 3:] == "020":
        print("YES")
    elif data[:2] == "20" and data[n - 2:] == "20":
        print("YES")
    elif data[:3] == "202" and data[n - 1:] == "0":
        print("YES")
    elif data[:4] == "2020":
        print("YES")
    else:
        print("NO")

 

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

 

  하나의 정수 x가 주어졌을 때, 각 자릿수의 합이 x가 되는 정수 중에서 가장 작은 수를 찾는 문제다. 이때 각 자릿수는 서로 달라야 한다. 예를 들어 x = 15일 때는 69가 정답이다. 이 문제의 해결 아이디어는 간단하다. 자릿수의 값을 최대한 크게 설정하면 값이 작아진다는 점을 이용하면 된다. 따라서 9부터 1까지 확인하면서 빼면 된다.

 

  참고로 45 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9이므로, 45보다 큰 수는 정답이 존재하지 않는다.

 

for _ in range(int(input())):
    x = int(input())
    # 45보다 큰 수는 정답이 없음
    if x >= 46:
        print("-1")
        continue
    result = []
    # 9부터 1까지의 수를 확인하며
    for i in range(9, 0, -1):
        if x >= i:
            result.append(i)
            x -= i
    result.sort()
    print(''.join([str(i) for i in result]))

 

D번 문제: codeforces.com/contest/1462/problem/D

 

  N개의 정수가 있다. 그리고 한 번의 연산을 통해 인접한 두 수끼리 합쳐질 수 있다고 한다. 결과적으로 모든 수가 같아지기까지의 최소 연산 횟수를 구하는 문제다. 예를 들어 [1, 2, 2, 1]이 있다고 하자. 이때 [1, 2, 2, 1] → [3, 2, 1] → [3, 3]으로 단 두 번의 연산이면 된다.

 

  이 문제는 알고 보니 정수론(number theory)이었던 문제다. 모든 수의 합을 summary라고 하자. 1부터 N 사이의 값 중에서 summary를 나누어 떨어뜨리는 것이 가능한 수들이 후보군이다. 예를 들어 summary = 12이고, N = 6이라고 해보자. 그러면 남아있는 수의 개수로는 1, 2, 3, 4, 6이 가능하다. 예를 들어 2의 경우에는 [6, 6]을 남기면 되는 것이다.

 

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 후보군(candidate) 찾기
    summary = sum(arr)
    candidates = []
    for i in range(n, 0, -1):
        if summary % i == 0:
            candidates.append(i)
    
    for candidate in candidates:
        target = summary // candidate
        # 모든 수가 target이 되도록 합칠 수 있는지 체크
        check = True
        value = 0
        for x in arr:
            value += x
            if value == target:
                value = 0
            # 합쳤을 때 target보다 크다면, 불가능한 케이스
            elif value > target:
                check = False
                break
        if check:
            print(n - candidate)
            break