Atcoder Beginner Contest 271 후기

A. 484558

 주어진 숫자를 16진수로 바꾸는 문제이다. 파이썬 기준으로는 간단히 내장함수로 처리할 수 있다. 약간 주의할 점은 leading zero를 채워줘야 한다는 것이고, 숫자가 아닌 문자에 대해서는 대문자로 항상 출력해야 한다는 점이다

import sys

n = int(sys.stdin.readline())
print(str(hex(n)).replace('0x', '').zfill(2).upper())

 

B. Maintain Multiple Sequences

 n개의 수열이 주어지고, m개의 쿼리가 들어온다. 이 때 쿼리의 형식은 두 숫자인데, 의미는 i번째 수열의 j번째 원소를 출력하라는 의미이다. 사실상 n개의 수열로 이루어진 2차원만 구성해주면 복잡도는 $O(N + M)$이기 때문에 여유있게 정답을 구할 수 있다

import sys

n, q = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
    _, *temp = list(map(int, sys.stdin.readline().split()))
    arr.append(temp)
for _ in range(q):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    print(arr[a][b])

 

C. Manga

 책이 n권 주어지고, 아무 책이나 2권을 고르면 원하는 책 한권과 바꿀 수 있다. 이 때 바꾸는 연산을 0번 이상 시행할 수 있다. 연산을 임의의 횟수대로 진행하고 1권, 2권, 3권의 순서대로 읽을 때 최대 몇번째 책까지 읽을 수 있는지 구하는 문제이다. 전형적인 이분 탐색 문제이다. 왜냐하면 "현재 x권까지 읽을 수 있는가?"에 대한 물음을 함수로 바꿔서 생각해보면, 목적함수는 단조증가함이 자명하기 때문이다. 즉, 만약 임의의 연산으로 1,2,3,4권까지 읽을 수 있다면 당연히 1,2,3권까지 읽을 수 있다는 것이다.

 따라서 어떻게 i권까지 읽을 수 있는지를 판단하는 것이 핵심이 되는데, 1부터 i까지의 숫자 중 수열에 존재하는 숫자를 저장한다. 이 때 저장되지 못한 수열의 원소는 바꿔야 하는 책이 되기 때문에 남은 수열의 갯수의 절반이 최대로 얻을 수 있는 책의 갯수가 된다. 따라서, 이 부분을 구현해주면 이분 탐색에 필요한 check 함수를 작성할 수 있다

import sys

# check : 1부터 num까지의 책을 읽을 수 있으면 true, 아니면 false를 리턴하는 함수
def check(num):
    # res : 1부터 num까지의 수 중 arr에 있는 수를 저장하는 set
    res = set()
    # cache : arr을 중복제거한 set
    cache = set(arr)
    for i in range(1, num + 1):
        # 현재 수가 cache에 있다면 저장
        if i in cache:
            res.add(i)
            
    # need : 교환을 통해 만들어야 하는 책의 수
    need = num - len(res)
    
    # cnt : 현재 교환할 수 있는 책의 갯수
    cnt = 0
    for i in range(n):
        # 굳이 교환할 필요가 없는 경우 res에서 삭제
        if arr[i] in res:
            res.remove(arr[i])
        else:
            cnt += 1
    return cnt // 2 >= need

# 입력부
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

# 이분탐색
left = 0
right = 1000000
while left < right:
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1
    else:
        right = mid
# 정답 출력
print(right - 1)

 

D. Flip and Adjust

 동전이 n개가 있고 앞면 혹은 뒷면을 뒤집어서 얻을 수 있는 점수가 있을 때 n개의 동전을 모두 뒤집은 후 얻은 점수의 총합이 s를 정확히 만족하는지, 만족한다면 n개의 동전을 어떻게 뒤집어야 하는지를 출력해야 하는 문제이다. 전형적인 bfs 혹은 0-1 dp이다. 이번 포스팅에서는 0-1 dp로 풀이하겠다

 0-1 dp의 경우는 일반적인 dp와 전혀 다를 것이 없다. 다만, 일반적인 dp의 경우 상태 공간에 저장하는 값이 보통 최대값, 최소값, 경우의 수이지만, 0-1 dp의 경우 상태 공간에 저장하는 값이 가능한지의 여부이다. 따라서 가질 수 있는 값이 0 혹은 1밖에 없다. n이 100이고 s가 10,000이기 때문에 상태 공간을 현재 점수가 now점이고 idx번째 동전의 status면을 뒤집어 정확히 s점을 얻을 수 있는지 여부라고 정의하자. 따라서 점화식은 아래와 같다. $$dp[idx][now][status] = max(dp[idx][now][status], dp[idx + 1][now + arr[idx][status]][status], \\ dp[idx + 1][now + arr[idx][status]][1 - status])$$

 단순히 가능한지의 여부뿐만 아니라 그때의 방법을 출력해야 하는 문제는 보통 상태 공간과 똑같은 크기의 배열을 만들어서 dp값이 갱신되는 순간에 방법을 저장하면 된다. 따라서 일반적인 dp문제를 풀 듯 함수를 작성하고 실행한 다음, 출력용 함수를 실행하면 된다

import sys
sys.setrecursionlimit(200000)

# go : 현재 누적점수가 now점이고 idx번째 동전의 status면을 뒤집을 때 정확히 점수가 s점이 되는지의 여부를
#      리턴하는 함수
def go(idx, now, status):
    # Base Case : 동전을 다 뒤집은 경우
    if idx == n:
        if now == s:
            return 1
        return 0
    # Memoization
    if dp[idx][now][status] != -1:
        return dp[idx][now][status]
    dp[idx][now][status] = 0
    # 점화식
    if now + arr[idx][status] <= s:
        dp[idx][now][status] = max(dp[idx][now][status], go(idx + 1, now + arr[idx][status], status), go(idx + 1, now + arr[idx][status], 1 - status))
    # 만일, 가능한 경우라면 뒤집는 방법 갱신
    if dp[idx][now][status] == 1:
        path[idx][now][status] = 'H' if not status else 'T'
    return dp[idx][now][status]

# display : 현재 누적점수가 now점이고 idx번째 동전의 status면을 뒤집을 때 정확히 점수가 s점이 될 때,
#           그 때의 방법을 출력하는 함수
def display(idx, now, status):
    # Base Case : 모든 동전을 다 뒤집었을 때
    if idx == n:
        return
    # 현재 idx번째 동전의 방법을 출력
    print(path[idx][now][status], end='')
    if idx != n - 1:
        # 다음 동전이 현재 동전과 같은 면으로 뒤집어야 조건을 만족하는 경우
        if path[idx + 1][now + arr[idx][status]][status] != -1:
            display(idx + 1, now + arr[idx][status], status)
        # 다음 동전이 현재 동전과 다른 면으로 뒤집어야 조건을 만족하는 경우
        else:
            display(idx + 1, now + arr[idx][status], 1 - status)

# 입력부
n, s = map(int, sys.stdin.readline().split())
arr = []

# dp : 현재 누적점수가 now점이고 idx번째 동전의 status면을 뒤집을 때 정확히 점수가 s점이 되는지의 여부를
#      저장하는 3차원 상태 공간 배열
dp = [[[-1] * 2 for _ in range(s + 1)] for _ in range(n)]

# path : 현재 누적점수가 now점이고 idx번째 동전의 status면을 뒤집을 때 정확히 점수가 s점이 될때의 방법을
#        저장하는 3차원 배열
path = [[[-1] * 2 for _ in range(s + 1)] for _ in range(n)]
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    arr.append((a, b))
    
# 첫번째 동전의 앞면을 뒤집어서 가능한 경우
if go(0, 0, 0):
    print('Yes')
    display(0, 0, 0)
# 첫번째 동전의 뒷면을 뒤집어서 가능한 경우 
elif go(0, 0, 1):
    print('Yes')
    display(0, 0, 1)
# 어떠한 경우로도 안되는 경우
else:
    print('No')

 

E. Subsequence Path

 양수의 가중치가 있는 방향 그래프가 주어지고, 간선 번호가 원소인 수열이 주어질 때 배열의 subarray들 중 1부터 n번 정점까지 갈 수 있는 경로 중 최소값을 묻는 문제이다. 만약 1부터 n번 정점까지 잘 수 있는 경로가 subarray에 없다면 -1을 출력하면 된다. subarray니까 dp로 풀 수 있다고 생각할 수 있으나, 상태 공간의 모델링이 메모리나 시간을 만족하는 크기로 모델링할 수 없다. 왜냐하면 필요한 정보는 현재 어떤 정점에 있고 수열의 몇번째 원소인지 알아야 하는데, n과 k가 모두 20만이기 때문이다. 다익스트라는 어떨까? 일반적인 최소 거리만 저장하는 dist배열이 아니라, 현재 정점에 오기 위해서 수열에서 몇번째 원소를 건너뛰었는지를 같이 저장하면 되지 않을까?

<그림 1. 예제 입력 1의 경우>

 위 그림 1은 위에서 설명한 다익스트라 풀이를 예제 입력 1의 경우에 대입한 그림이다. 그래프는 좌측에 있으며 현재 빨간 간선을 보자. 빨간 간선은 1에서 2로 가면서 가중치가 2인 간선이다. 이 때 괄호안의 숫자의 의미는 해당 간선이 전체 간선들 중 몇번째 인지를 나타내는 수이다. arr은 입력으로 주어지는 간선 번호들로 이루어진 수열이다. cache의 경우는 arr에서 출현하는 간선 번호를 key, arr상에서 해당 간선 번호의 인덱스 리스트(오름차순)를 value로 갖는 dictionary이다. 마지막으로 밑에 있는 heap은 다익스트라를 구현하기 위한 최소 힙이다. 이 때 힙에 저장되는 정보는 현재까지의 누적 거리, 현재 정점, arr상에서의 위치로 총 3가지의 정보를 갖는다.

 우선, 1에서 2로 가는 상황, 즉 1번 간선을 타는 상황을 생각해보자. 현재 1번 간선의 cache값 중 -1보다 큰 수는 2이다. 따라서, 2까지의 거리를 갱신하고 heap에 추가한다

<그림 2. 예제 입력 1의 경우>

  위 그림 2는 1번 정점에서 3번 정점, 즉 4번 간선을 타는 경우의 그림이다. 현재 1번 정점이고 arr상에서의 간선의 위치가 -1이다. 따라서 4번 간선의 cache값 중 -1보다 큰 수는 0이고 dist[3]이 inf이기 때문에 거리를 갱신하고 heap에 추가한다. 3번 간선의 경우는 어떨까? 비록 그래프 상에서는 존재하는 간선이나, cache에 없기 때문에 즉, arr에 존재하는 간선 번호가 아니기 때문에 힙에 추가되지 않는다

<그림 3. 예제 입력 1의 경우>

 위 그림 3은 정점 2번에서 정점 3번으로 가는 간선, 즉 2번 간선의 경우를 나타낸 그림이다. 현재 2번 정점에 있고 이때까지의 거리가 2였으며, arr상에 위치가 2일 때, 2번 간선의 cache값 중 2(arr상의 위치)보다 큰 값은 3이고 dist[3]의 값이 2 + 2보다 작기 때문에 정점 3의 거리를 갱신하고 힙에 추가한다. 따라서, 우리는 arr의 subarray중 [1,2]라는 부분 배열로 이루어진 경로를 이용해 1부터 3까지 4의 거리만에 도달할 수 있다. 즉, 위 그림들에 적용한 풀이의 핵심은 현재 정점에 오기 위해 마지막으로 사용한 간선의 인덱스보다 무조건 이후의 인덱스를 가지는 간선을 사용하므로서 자연스럽게 subarray의 조건을 만족함에 있다. 단, 현재 간선의 인덱스보다 더 큰 인덱스가 많을 경우에는 uppper bound를 이용하여 그 중에서 가장 작은 값을 얻도록 하였다

<그림 4. 반례>

 위 그림 4는 제시한 다익스트라 풀이의 반례이다. 다익스트라 풀이에 의해 접근한다면 현재 3번 간선, 즉 정점 1번에서 정점 3번으로 가는 간선을 타는 경우는 힙에 추가할 수 있으므로 거리를 갱신하면서 힙에 추가한다

<그림 5. 반례>

 위 그림 5에서는 4번 간선, 즉 정점 1번에서 정점 2번으로 가는 간선을 타는 경우를 나타낸 그림이다. 다익스트라 풀이에 따라 subarray를 만족하면서 거리 조건까지 만족하기 때문에 거리를 갱신하고 힙에 추가한다

<그림 6. 반례>

 위 그림 6은 현재 정점이 3인 경우를 나타낸 그림이다. 이 때 역시나 1번 간선, 즉 3번 정점에서 2번 정점으로 가는 경우를 생각해보자. 현재 정점 3번까지 오기 위해 이용한 마지막 간선은 3번 간선이고, 3번 간선은 arr상에서 0번째 인덱스에 위치해 있다. 따라서, 1번 간선은 arr상에서 1번째 인덱스에 위치하고 있으므로 subarray를 만족하나, 거리 조건을 만족하지 못해, 즉 1 + 7은 5보다 작기 때문에 힙에 추가할 수 없다.

<그림 7. 반례>

위 그림 7은 현재 정점이 2인 경우를 나타낸 그림이다. 이 때 역시나 2번 간선, 즉 2번 정점에서 4번 정점으로 가는 경우를 생각해보자. 현재 정점 2번까지 오기 위해 이용한 마지막 간선은 4번 간선이고, 4번 간선은 arr상에서 3번째 인덱스에 위치해 있다. 그러나, 2번 간선은 arr상에서 2번째 인덱스에 위치하기 때문에 거리 조건을 만족하더라도 subarray를 만족하지 못해 힙에 추가할 수 없다. 따라서, 다익스트라 풀이에 따르면 현재 그래프는 조건을 만족하면서 1번 정점부터 4번 정점까지 갈 수 없게 된다. 그러나, 실제로는 subarray가 [3,1,2]인 경우에 11의 거리만큼 이동하면 조건을 만족하기 때문에 다익스트라의 정합성에 오류가 발생한다

 결국 모든 subarray들을 다 살펴봐야 위와 같은 반례가 있어도 정답을 구할 수 있다. 따라서 이 문제는 일반적인 다익스트라가 아닌 다이나믹 프로그래밍 문제로 풀어야 한다. 상태 공간은 현재 idx번째 간선일 때, 시작점 혹은 끝점까지 가기 위해 필요한 최단 거리라고 정의하자. 따라서, 점화식은 다음과 같다. $$dp[end[idx]] = min(dp[end[idx]], dp[start[idx]] + cost[idx]) $$ 이 때 start와 end, cost는 각각 idx번째 간선에 대한 시작점과 끝점, 그리고 비용을 저장하는 1차원 배열이다. 이는 subarray를 구성하려면 인덱스가 증가하는 속성을 이용한 것으로 다이나믹 프로그래밍의 상태 공간이 $O(NK)$가 아니라, $O(N)$만큼의 공간 복잡도를 가지게 된다. 특이한 점은 결국 간선에 따라 상태 공간이 변이하므로 시간 복잡도는 $O(K)$가 된다. 따라서, 시간안에 정답을 구할 수 있다

import sys

# 입력부
n, m, k = map(int, sys.stdin.readline().split())
inf = 98765432109876543210
start, end, cost = [], [], []

# dp : 현재 idx번째 간선일 때, 시작점 혹은 끝점까지 가기 위해 필요한 최단 거리를 저장하는 1차원 상태 공간 배열
dp = [inf] * n
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    start.append(a)
    end.append(b)
    cost.append(c)
# arr : 간선 번호를 저장하는 배열
arr = list(map(int, sys.stdin.readline().split()))

# 시작점 초기화
dp[0] = 0
# 점화식
for i in arr:
    i -= 1
    dp[end[i]] = min(dp[end[i]], dp[start[i]] + cost[i])
    
# 정답 출력
print(-1 if dp[n - 1] == inf else dp[n - 1])

 

 후기 : 푼 시간은 11월로 기억하나, 노느라 바빠서 포스팅을 이번에 올린다. A번부터 D번까지는 무난했으나 D에서 구현이 꼬여버려서 시간을 많이 지체한 버추얼이었다. E번의 경우는 대회 중 접근한 다익스트라 풀이가 정해라고 생각했으나, 반례 생성 코드를 통해 반례를 찾았다. 그러나 이후에도 큰 사고의 전환이 이루어지지는 않아서 에디토리얼을 보았는데 상태 공간을 1차원으로 모델링한 것을 보고 매우 흥미롭다고 생각했다. 보통 dp의 경우는 상태 공간에 쓰이는 변수들이 보통 직접적으로 쓰이기 마련인데, 이번 문제는 한번 꼬아서 생각해야 풀리는 문제였기 때문에 재밌었다! 앞으로도 꾸준히 버추얼을 해야겠다