Atcoder Beginner Contest 265 후기

A. Apple

 단순한 구현 문제이다. 사과를 1개 살 때 X만큼의 비용이 들고 3개 살 때는 Y만큼의 비용이 들 때 전체 N개를 살 때 최소 비용을 묻는 문제이다. X, Y, N 모두 100이하이기 때문에 단순 for문으로 처리 가능하다

import sys

x, y, n = map(int, sys.stdin.readline().split())
ans = 9876543210
for i in range(n):
    if n - 3 * i >= 0:
        ans = min(ans, y * i + x * (n - 3 * i))
print(ans)

 

B. Explore

 역시 단순한 구현 문제이다. 1부터 N번방까지 순차적으로 방문하는데, 방을 이동할 때 마다 시간이 감소된다. 현재 남은 시간이 0이하면 더 이상 움직일 수 없다. 특정 보너스 방에 도달하면 시간 제한이 추가되는 조건이 있다. N번방까지 도달할 수 있는지는 단순한 for문으로 처리 가능하다

import sys

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

# val : 보너스 방의 번호를 key, 그 때의 추가 시간을 value로 갖는 dict
val = dict()

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    val[a] = b
    
for i in range(len(arr)):
    start, end = i + 1, i + 2
    # 현재 방이 보너스 방인 경우 시간 추가
    if start in val:
        t += val[start]
    # 방을 이동하는 도중 잔여 시간이 0이하인 경우 No 출력
    if t - arr[i] <= 0:
        print('No')
        sys.exit(0)
    # 방을 이동해도 잔여 시간이 0 초과인 경우는 잔여 시간 차감
    else:
        t -= arr[i]
# 모든 방을 통과할 수 있으면 Yes 출력
print('Yes')

 

C. Belt Conveyor

 현재 서 있는 부분의 글자에 따라 동서남북의 4방향 중 한 방향으로 움직일 때 가장 마지막에 도달하는 좌표를 출력하는 문제이다. 다만, 사이클이 있어서 무한히 순환한다면 -1을 출력하면 된다. 2차원 격자이고 N, M 제한이 작기 때문에 단순한 bfs로 풀면 된다. 사이클의 경우는 현재 좌표에서 다음 좌표로 이동할 때 방문한 적이 있는 정점이면 사이클이므로 쉽게 판별할 수 있다

import sys, collections

# 입력부
n, m = map(int, sys.stdin.readline().split())
arr = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
q = collections.deque()

# cache : 방향을 key, 그 때 x, y의 단위 벡터를 value를 갖는 dict
cache = {'R' : (0, 1), 'D' : (1, 0), 'L' : (0, -1), 'U' : (-1, 0)}

# vis : 2차원 방문 배열
vis = [[False] * m for _ in range(n)]
vis[0][0] = True
q.append((0, 0))

# px, py : 마지막 좌표
px, py = -1, -1
while q:
    x, y = q.popleft()
    px, py = x, y
    # nx, ny : 다음 위치의 좌표
    nx, ny = x + cache[arr[x][y]][0], y + cache[arr[x][y]][1]
    # 다음 좌표가 범위를 벗어나지 않는다면
    if 0 <= nx < n and 0 <= ny < m:
    	# 이미 방문한 곳이 다음 좌표라면 순환하므로 -1 출력
        if vis[nx][ny]:
            print(-1)
            sys.exit(0)
        # 새로 방문하는 경우
        else:
            vis[nx][ny] = True
            q.append((nx, ny))
            
# 마지막 좌표 출력
print(px + 1, py + 1)

 

D. Iroha and Haiku (New ABC Edition)

 길이가 N인 배열이 주어지고,  $ \sum_{i=x}^{y-1} A_i = P, \ \sum_{i=y}^{z-1}A_i = Q, \ \sum_{i=z}^{w-1} A_i = R $을 만족하고 또한 $ 0 \leq x < y < z < w \leq N $를 만족하는 순서쌍 (x, y, z, w)를 구하는 문제이다. x,y,z,w를 모두 구하는 브루트포스로는 $ O(N^4) $ 이므로 절대로 시간안에 정답을 도출할 수 없다. 따라서 최적화가 필요하다

 사실, 실제 (x, y, z, w)를 구할 필요가 없다는 점에 주목하자. 따라서 현재 위치 i에서 다음 위치 j-1까지의 합이 단순히 P인지, Q인지, R인지만 알면 된다. 따라서, 누적합이 필요함을 알 수 있다. 누적합을 이용하면 특정 구간의 합을 O(1)만에 구할 수 있기 때문이다.

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

 위 그림 1에서 현재 위치를 now라고 하자. 그런데, now부터 y-1까지의 합이 5가 되는 구간은 없다. 왜냐하면 누적합의 정의에 따라서, pf[y - 1] - pf[now -1] = 5인 y지점이 없기 때문이다. (pf[-1]은 편의상 0으로 하자) 따라서, now를 한칸 옮기자

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

 현재 now에서 y-1까지의 합이 5가 되는 구간은 y가 3인 경우이다. 왜냐하면 pf[3 - 1] - pf[1 - 1] = 5이기 때문이다. 따라서, cnt를 증가시킨다. 이 때 cnt가 3인 경우가 x, y, z, w를 찾은 경우이다.

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

 현재 now에서 z-1까지의 합이 7가 되는 구간은 z가 6인 경우이다. 왜냐하면 pf[6 - 1] - pf[3 - 1] = 7이기 때문이다. 따라서, cnt를 증가시킨다.

<그림 4. 문제에서의 예제 입력 1의 경우>

 현재 now에서 w-1까지의 합이 5가 되는 구간은 w가 8인 경우이다. 왜냐하면 pf[8 - 1] - pf[6 - 1] = 5이기 때문이다. cnt를 증가시킨 순간, cnt가 3이 되기 때문에 원하는 순서쌍을 찾게 된다. 따라서 더이상의 탐색을 종료하고 Yes를 출력하면 된다.

 그런데, 이렇게 하기 위해서는 하나의 장치가 추가적으로 더 필요하다. 현재 위치를 idx라고 하자. 그렇다면, pf[idx - 1] + a(a는 P, Q, R 중 하나)가 있는지 없는지를 O(1)만에 판별하는 장치가 필요하다. 그러한 역할을 하는 것은 set이나 map(dictionary)일 수 있다. 그런데 set보다는 map이 더 적절하다. 이유는 있는지 없는지 뿐만 아니라, pf[idx - 1] + a의 위치가 다음 idx가 되기 때문이다. 따라서, key를 pf의 원소로 갖고 value를 그 때의 인덱스를 갖는 dictionary를 전처리하여야 $O(N)$만에 정답을 구할 수 있다. 

 만일 그런 순서쌍이 없는 경우는 어떻게 구할까? 간단하다. 배열을 끝까지 탐색했음에도 cnt가 3이 아니라면 찾지 못했으므로 No를 출력하면 된다.

import sys

# 입력부
n, p, q, r = map(int, sys.stdin.readline().split())
val = [p, q, r]
arr = list(map(int, sys.stdin.readline().split()))

# pf : 누적합 배열
pf = [0] * n
pf[0] = arr[0]
for i in range(1, n):
    pf[i] = pf[i - 1] + arr[i]
    
# pf[-1]을 위한 처리
pf.append(0)

# cache : pf의 원소를 key, 그 때의 위치를 value로 갖는 dict
cache = dict()
for i in range(n):
    cache[pf[i]] = i
    
for i in range(n):
    # idx : 현재 위치, cnt : 현재까지 찾은 갯수, now : 현재의 누적합
    idx = i
    cnt = 0
    now = pf[i]
    
    # 현재 위치가 n미만이고 아직 순서쌍을 모두 찾지 못한 경우
    while idx < n and cnt < 3:
        # 현재 위치에서 조건을 만족하여 다음 위치로 갈 수 있다면
        if pf[idx - 1] + val[cnt] in cache:
            # idx를 이동한 후 1칸 더 이동
            idx = cache[pf[idx - 1] + val[cnt]] + 1
            # now, cnt 갱신
            now = pf[idx]
            cnt += 1
        # 현재 위치에서 조건을 맍족하여 다음 위치로 갈 수 없다면 탈출
        else:
            break
    # 순서쌍을 찾은 경우 정답 출력
    if cnt == 3:
        print('Yes')
        sys.exit(0)
        
# 순서쌍을 찾지 못한 경우에도 정답 출력
print('No')

 

E. Warp

 초기 위치가 (0, 0)이고, 총 N번의 순간이동을 한다. 다만, M개의 장애물이 있는 좌표로는 순간이동을 할 수 없다. 순간이동에는 총 3가지 중 하나의 방법을 택하는데, 현재 위치가 (x, y)라면, 첫번째로 (x + a, x + b)로 순간이동을 하는 경우이다. 두번째는 (x + c, x + d)로 이동하는 경우이다. 세번째는 (x + e, x + f)로 이동하는 경우이다.

 전형적인 다이나믹 프로그래밍 문제이다. 따라서 상태 공간을 정의하면 된다. 그런데, 상태 공간을 현재 idx번째 순간이동을 하고 현재 위치가 (x, y)일 때 가능한 경우의 수인 dp[idx][x][y]라고 정의하면 메모리 초과를 피할 수 없다. 왜냐하면 순간 이동을 할 때 (x, y)의 좌표가 각각 $10^9$이 될 수 있기 때문이다. 따라서 현재 좌표를 가지고 상태공간을 모델링해서는 안된다.

 그런데, 현재 좌표를 가지지 않고 다음 좌표를 구할 수 없다. 다음 좌표를 구할 수 없으면 해당 순간이동이 장애물로 가는 경우인지 아닌지를 판단할 수 없다. 어떻게 해야할까?

 방법은 꽤나 간단하다. 이미 상태 전이가 주어졌기 때문에, 현재까지 순간이동했을 때 각 방법의 횟수를 안다면 현재 좌표를 계산할 수 있다. 따라서, 상태공간을 현재 idx번째 순간이동을 하고 첫번째 방법을 first, 두번째 방법을 second번 사용했을 때 가능한 방법의 수라고 정의하자. 여기서 왜 세번째 방법을 third로 하지 않는지 궁금할 것이다. 이유는 third까지 상태 공간에 부여하게 되면, $ O(N^4)$가 되기 때문에 메모리 초과를 피할 수 없기 때문이다. 그런데 첫번째 방법과 두번째 방법을 각각 몇 번 썼는지 알고, 전체 횟수를 알면 세번째 횟수는 계산할 수 있다. 가령, 현재까지 5번 순간이동을 했고, 첫번째 방법을 1번 썼고, 두번째 방법을 2번 썼다고 하자. 따라서 세번째 방법은 5-1-2인 2가 됨은 자명하다. 따라서 메모리 초과없이, 시간초과 없이 다이나믹 프로그래밍으로 정답을 구할 수 있다

import sys

# go : 현재 idx번째 순간이동을 하고, 첫번째 방법을 총 first번, 두번째 방법을 총 second번 썼을 때 
#      가능한 경우의 수를 리턴하는 함수
def go(idx, first, second):
	# Base Case : 모든 순간이동이 끝난 경우
    if idx == n:
        return 1
    # Memoization
    if dp[idx][first][second] != -1:
        return dp[idx][first][second]
    dp[idx][first][second] = 0
    
    # x, y : 현재 위치
    x, y = first * a + second * c + (idx - first - second) * e, first * b + second * d + (idx - first - second) * f
    
    # 첫번째 순간이동을 해도 장애물이 없다면 이동
    if (x + a, y + b) not in cache:
        dp[idx][first][second] += go(idx + 1, first + 1, second)
    # 두번째 순간이동을 해도 장애물이 없다면 이동
    if (x + c, y + d) not in cache:
        dp[idx][first][second] += go(idx + 1, first, second + 1)
    # 세번째 순간이동을 해도 장애물이 없다면 이동
    if (x + e, y + f) not in cache:
        dp[idx][first][second] += go(idx + 1, first, second)
    dp[idx][first][second] %= mod
    return dp[idx][first][second]


# 입력부
n, m = map(int, sys.stdin.readline().split())
a, b, c, d, e, f = map(int, sys.stdin.readline().split())

# cache : 장애물의 위치를 저장하는 set
cache = set()
for _ in range(m):
    p, q = map(int, sys.stdin.readline().split())
    cache.add((p, q))
    
# dp : 현재 idx번째 순간이동을 하고, 첫번째 방법을 총 first번, 두번째 방법을 총 second번 썼을 때 
#      가능한 경우의 수를 저장하는 3차원 상태 공간 배열
dp = [[[-1] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
mod = 998244353

# 정답 출력
print(go(0, 0, 0))

 

후기 : 우테코 레벨 3를 끝낸 이후 처음으로 치는 앳코더였다. 솔직히 쫄려서 언레로 등록했는데...그런데... 역대급 점수를 찍어버려서 매우 후회 중이다. 실력이 늘었다라기 보다는 운이 좋았다고 생각한다. 특히 E번을 원큐에 맞춘게 기뻤다. 다만, 너무 술술 풀려서 풀면서도 이상하는 느낌을 지울 수 없던 셋이다. 앞으로도 이랬으면 좋겠는데 아마 잘 안될거라는 걸 안다.. 

 아쉬운 점은 B를 한번 틀렸다는 경우인데 너무 안이하게 제출했다가 쓸데 없는 페널티를 먹었다. 이것만 아니었더라도 등수가 더 올랐을 거 같은데 아쉽다!