대회 링크: https://codeforces.com/contest/1352

A번 문제: https://codeforces.com/contest/1352/problem/A

[ 문제 해설 ]

  이 문제는 먼저 각 자릿수를 확인하면 된다. 이 때, 0이 아닌 자릿수에 대하여 그 값들을 출력해주면 된다. 예를 들어 입력이 6009이라면, 6000과 9를 출력하면 된다. 소스코드는 다음과 같다.

[ 정답 코드 ]

for _ in range(int(input())):
    n = int(input())
    result = []

    power = 1
    # 각 자릿수를 확인하며
    while n > 0:
        # 0이 아닌 자릿수에 대하여
        if n % 10 != 0:
            # 그 값들을 각각 출력
            result.append((n % 10) * power)
        n //= 10
        power *= 10
  
    print(len(result))
    for i in result:
        print(i, end=' ')
    print()

B번 문제: https://codeforces.com/contest/1352/problem/B

  이 문제는 k개의 수를 더해서 n을 만들 수 있는지 물어보는 문제이다. 단, k개의 수는 모두 홀수이거나 모두 짝수여야 한다.

[ 문제 해설 ]

  문제에서 요구하는 대로 모든 수가 홀수이거나, 모든 수가 짝수인 경우 두 가지만 고려하면 된다.

  먼저 모든 수가 홀수인 경우, (k - 1)개의 수를 모두 1로 설정(가능한 작은 수)한 뒤에  '나머지 1개의 수'가 홀수이면서 조건을 만족시킬 수 시 있는지 확인하면 된다.  예를 들어 n = 7, k = 5인 경우에는 (k - 1) + 3 = 7로 n을 만족시킬 수 있다. 즉, 나머지 1개의 수를 3으로 설정하면 된다.

  그리고 모든 수가 짝수인 경우, (k - 1)개의 수를 모두 2로 설정(가능한 작은 수)한 뒤에  '나머지 1개의 수'가 짝수이면서 조건을 만족시킬 수 있는지 확인하면 된다. 예를 들어 n = 8, k = 3인 경우에는 (k - 1) * 2 + 4 = 8로 n을 만족시킬 수 있다. 즉, 나머지 1개의 수를 4로 설정하면 된다.

  따라서 두 가지 경우만 잘 고려해주는 코드를 작성하면 된다.

[ 정답 코드 ]

for _ in range(int(input())):
    n, k = map(int, input().split())

    # 모든 수가 홀수인 경우
    odd = n - (k - 1)
    if odd > 0 and odd % 2 == 1:
        print("YES")
        for i in range(k - 1):
            print(1, end=' ')
        print(odd)
        continue

    # 모든 수가 짝수인 경우
    even = n - (k - 1) * 2
    if even > 0 and even % 2 == 0:
        print("YES")
        for i in range(k - 1):
            print(2, end=' ')
        print(even)
        continue

    # 두 가지 케이스 모두 만족시킬 수 없을 때
    print("NO")

C번 문제: https://codeforces.com/contest/1352/problem/C

  n과 k가 주어졌을 때, n으로 나누어 떨어지지 않는 k번째 자연수를 찾으면 되는 문제다. 

  예를 들어 n = 3, k = 7이라고 하면

  1, 2, 4, 5, 7, 8, 10, 11, 13, ... 

  위와 같이 이어지므로, 7번째 수는 바로 10이 된다.

[ 문제 해설 ]

  답을 구하는 방법은 생각보다 쉽다. 구하고자 하는 k번째 자연수는 항상 k 이상이고, 그리고 2k 미만이 된다.

  생각해 보면, n = 2일 때는 1, 3, 5, 7, ... 이렇게 갈 텐데, 이 때에도 k번째 수는 2k보다 작은 2k - 1이 된다. 다시 말해 출력해야 되는 정답은 항상 k 이상 2k 미만의 수가 될 것이다. 그렇다면 k보다 얼마나 큰 수가 출력되어야 하는가?

  그것은 바로 k보다 (k - 1) // (n - 1)만큼만 커지면 된다. 즉, k + (k - 1) // (n - 1)이 정답이다. 답을 계산하는 방법은 굉장히 다양하지만, 이것보다 간단히 수식으로 표현할 수 있는 답은 없다.

[ 정답 코드 ]

for _ in range(int(input())):
    n, k = map(int, input().split())
    print(k + (k - 1) // (n - 1))

D번 문제: https://codeforces.com/contest/1352/problem/D

  왼쪽에서부터 오른쪽으로 과자를 먹는 사람과 오른쪽에서부터 왼쪽으로 과자를 먹는 사람이 있다. 

  이 때 한 차례씩 반복하면서 먹어나가는데, 이전 차례에서 상대방이 먹었던 양보다 더 많이 먹어야 하는 방식이다. 그래서 전체 몇 차례나 반복되었는지, 두 사람이 각각 얼마나 먹었는지를 출력하면 된다.

[ 문제 해설 ]

  이 문제는 문제에서 요구하는 대로 구현만 잘 해주면 된다. 최대한 깔끔하게 실수 없이 구현해서 정답 처리를 받으면 된다.

[ 정답 코드 ]

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    l = 0
    r = n - 1
    left_sum, right_sum = 0, 0
    left_res, right_res = 0, 0
    count = 0

    # 일종의 투 포인터(Two Pointers) 기법
    while l <= r:
        # 왼쪽에서 먹을 차례
        if count % 2 == 0:
            now_sum = 0
            while l <= r and now_sum <= right_sum:
                now_sum += data[l]
                l += 1
            left_res += now_sum
            left_sum = now_sum
        # 오른쪽에서 먹을 차례
        elif count % 2 == 1:
            now_sum = 0
            while l <= r and now_sum <= left_sum:
                now_sum += data[r]
                r -= 1
            right_res += now_sum
            right_sum = now_sum
        count += 1

    print(count, left_res, right_res)

E번 문제: https://codeforces.com/contest/1352/problem/E

  n개의 정수로 구성된 수열이 있을 때, 각 n개의 수에 대하여 그 수와 동일한 합을 가지는 '부분 연속 수열'이 존재하는지 찾으면 되는 문제이다.

  예를 들어 [3, 1, 4, 1, 5, 9, 2, 6, 5]가 있을 때 6번째 수인 9는 [3, 1, 4, 1]의 합과 같다.

[ 접근 방법 1 ]

  일단 이 문제는 투 포인터(Two Pointer)를 이용하여 해결할 수 있다. n개의 수 각각에 대하여 투 포인터 알고리즘을 돌리면 된다. 투 포인터 문제로 유명한 '합이 M인 부분 연속 수열 찾기' 코드를 그대로 쓰면 된다.

  단, 이 문제에서는 부분 연속 수열의 길이가 2 이상이 되라고 하였으므로 투 포인터 알고리즘을 길이가 2 이상인 경우만 찾도록 수정해서 이용하면 된다.

  코드포스 문제를 풀다 보면, 투 포인터 문제가 굉장히 자주 나오는 것 같다. 혹은... 내가 그냥 해법으로 투 포인터를 먼저 생각해서 그러는 거일 수도 있겠다. 근데 이게 가끔은 시간 초과를 받는 경우도 있으니 조심해야 한다.

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

    for x in data:
        summary = 0
        end = 0

        for start in range(n):
            while summary < x and end < n:
                summary += data[end]
                end += 1
            if summary == x and end - start >= 2:
                result += 1
                break
            summary -= data[start]

    print(result)

  근데... 걱정했던 대로 위 코드는 시간초과를 받았다. 투 포인터를 이용할 때에도 사실 O(N^2)의 해법으로 시간 복잡도가 똑같기 때문에 괜찮을 줄 알았는데, 파이썬을 이용하고 있기 때문인지... 시간 초과를 받을 줄은 몰랐다. ㅠㅠ 시간 초과를 받은 케이스를 보니까 정말 간발의 차이로 시간 초과를 받았다. 0.5초만 더 널널했어도, 시간 초과를 받지 않았을 것 같다.

[ 접근 방법 2 ]

  아무튼 같은 O(N^2)이지만, 조금 더 빠른 해법은 모든 구간의 합을 하나의 배열에 기록해 놓는 방법이다. (계수 정렬 할 때 처럼) 모든 값들이 n (1 <= n <= 8000) 보다 작기 때문에 이 또한 가능하다. 시간 초과에 걸리지 않는, 정답 코드는 다음과 같다.

[ 정답 코드 ]

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

    # 모든 구간 합을 저장하기 위한 집합 자료형
    visited = set()

    # 길이가 2 이상인 모든 구간 합을 집합에 저장
    for i in range(n):
        summary = data[i]
        for j in range(i + 1, n):
            summary += data[j]
            if summary > n:
                break
            visited.add(summary)

    # 각 값을 확인하며, 계산할 수 있는 구간 합인 경우 카운트
    result = 0
    for x in data:
        if x in visited:
            result += 1

    print(result)

F번 문제: https://codeforces.com/contest/1352/problem/F

[ 문제 해설 ]

  이 문제도 구현 문제인데, 최대한 구현 실수가 발생하지 않게 깔끔한 아이디어로 푸는 것이 중요하다. 일단 가장 중요한 게 n1 = 0인 케이스이다. 이 때는 n0과 n2 둘 중에 하나는 0이 되어야 한다. 안 그러면 조건이 만족되지 않는다. 따라서 n1 = 0인 경우에는, 단순히 n0과 n2 중에 하나만 0이 아닌 값을 가진다는 것을 고려해서 풀면 된다.

  그리고 n1 = 0인 케이스가 아니라면, 다음과 같이 먼저 처리해서 문제를 해결할 수 있다.

  해결법은 바로 다음과 같다. 먼저 (n2 + 1)의 크기만큼 1을 출력한다. 그리고 n0의 크기만큼 0을 출력한다. 이후에 n1의 크기만큼 010101... 을 반복해서 출력하면 된다. 그러면 정확히 조건을 만족할 수 있다.

[ 정답 코드 ]

for testcase in range(int(input())):
    n0, n1, n2 = map(int, input().split())
    
    # n1가 0인 특이 케이스 처리
    if n1 == 0:
        if n0 > 0:
            print("0" * (n0 + 1))
        else:
            print("1" * (n2 + 1))
        continue

    # 일반적인 케이스 처리
    print("1" * (n2 + 1), end="")
    print("0" * n0, end="")
    for i in range(n1):
        if i % 2 == 0:
            print("0", end="")
        else:
            print("1", end="")
    print()

G번 문제: https://codeforces.com/contest/1352/problem/G

[ 문제 해설 ]

  이 문제도 간단한 아이디어를 떠올리면 간단히 풀 수 있다. 필자는 대회 당시에는 매우 복잡하게 푼 것 같은데, 실제로는 매우 간단하게도 문제를 해결할 수 있었다.

  홀수를 먼저 내림차순으로 출력한 뒤에 4와 2를 출력하고, 다시 모든 짝수를 오름차순으로 차례대로 출력하면 된다. 이렇게 대칭을 이루도록 출력하면 간단하게 해결된다.

  예를 들어 n = 11이라고 하면,

  [ 11 9 7 5 3 1 ] [ 4 2] [6 8 10]로 출력하면 된다.

  위 출력 결과를 보면 인접한 모든 수들은 2 이상, 4 이하로 차이가 난다.

[ 정답 코드 ]

for _ in range(int(input())):
    n = int(input())
    # 4보다 작은 경우, 만들 수 없음
    if n < 4:
        print(-1)
        continue
  
    # 모든 홀수를 먼저 내림차순으로 출력
    for i in range(n, 0, -1):
        if i % 2 == 1:
            print(i, end=' ')
    # 4와 2를 출력
    print(4, 2, end=' ')
    # 모든 짝수를 오름차순으로 출력
    for i in range(6, n + 1, 2):
        print(i, end=' ')
    print()