[엣코더] AtCoder Beginner Contest 445 후기

처음으로 엣코더 응시를 해 보았다.

온라인 코테 응시가 처음이라 신기했다. 당연히 초보자 난이도로 응시했고, 증말 어려웠지만 문제 운이 좋아서 4/7솔에 성공했다. 어학연수 핑계로 6주 동안 백준 잔디밭에 숭숭 구멍이 뚫려서 3솔은 할 수 있을까 걱정이었는데, 생각보다 결과가 괜찮아서 만족스럽따.

 

응시한 코테는 abc 445 이다.

https://atcoder.jp/contests/abc445

AtCoder Beginner Contest 445 - AtCoder

 

처음에 시작하고 UI 적응이 안 되어서 5분 정도 날려먹었다. 찾아보니 연습용 응시 테스트가 있었다. 틀렸을 때 CE, RE 이런 식으로 뜨는 라벨이 있는데, 컴파일 오류, 런타임 오류, 시간 초과 등등을 의미한다. 이런 라벨들에 대한 설명도 하단 링크에 함께 있다. 엣코더가 처음이라면 시작 전에 한 번 둘러보는게 좋을 듯 하다.

https://atcoder.jp/contests/practice

practice contest - AtCoder

 

 

# A문제

https://atcoder.jp/contests/abc445/tasks/abc445_a

A - Strong Word

첫 문제는 간단하게 입력받은 문자열의 앞과 뒤의 문자가 같은지 틀린지 판별하는 문제였다.

import sys
input = sys.stdin.readline

s = input().strip()

if s[0] != s[-1] : 
    print("No")
else :
    print("Yes")

쉽게 해결 가능하다.

 

# B문제

https://atcoder.jp/contests/abc445/tasks/abc445_b

B - Center Alignment

문자열을 여러개 입력받고, 형식에 맞춰 출력하는 문제이다. 입력받은 문자열 중 가장 긴 문자열에 맞춰, 다른 짧은 문자열들의 앞 뒤에 "."을 여러개 붙여 가장 긴 길이에 맞추는 문제이다.

맨 처음 문제를 봤을 때 가장 먼저 들었던 생각은 '문자열 길이가 짝수면 어떡하지?' 이었다. 하지만 문제를 다시 한 번 잘 읽어보면 문자열 길이는 홀수라는 제한이 있다. 영어 코테의 함정

import sys
input = sys.stdin.readline

n = int(input())
strings = [input().strip() for _ in range(n)]

# 최대 문자열 길이 구하기
m = 0
for i in range(n) :
    s = strings[i]
    s_len = len(s)
    if s_len > m :
        m = s_len

# 출력 처리
for i in range(n) :
    s = strings[i]
    dots = (m - len(s)) // 2
    print(dots * "." + s + dots * ".")

입력받은 n개의 문자열 중 최대 문자열의 길이를 구한다. 코드에서는 m에 저장했다.

그리고 다시 한 번 입력 문자열 리스트(strings)를 돌면서, 최대 문자열 길이에 맞춰 길이가 부족하다면 앞 뒤에 "."을 붙여서 출력하면 된다.

 

# C문제

https://atcoder.jp/contests/abc445/tasks/abc445_c

C - Sugoroku Destination

- 문제 설명

1번 칸, 2번 칸, ... , N번 칸까지 총 N개의 칸이 일렬로 나열되어 있습니다. i번째 칸에는 정수 Ai (i <= A_i <= N)가 적혀 있습니다.

각 s = 1, 2, ... , N에 대하여 다음 문제를 해결하세요.

처음에 말(piece)을 s번 칸에 놓습니다. "말이 놓여 있는 칸에 적힌 정수를 x라 할 때, 말을 x번 칸으로 옮긴다"라는 조작을 10^100번 수행한 후, 말이 놓여 있는 칸의 번호를 출력하세요.

 

- 제약 사항

1 <= N <= 5*10^5

i <= Ai <= N (1 <= i <= N)

입력으로 주어지는 모든 값은 정수입니다.

 

- 예제입력1

7
2 4 7 5 5 6 7

 

- 예제출력1

5 5 7 5 5 6 7

 

- 예제입력2

5
1 2 3 4 5

 

- 예제출력2

1 2 3 4 5

말이 한 번도 움직이지 않을 수도 있습니다.

 

C번부터 조큼 어려워지기 시작했다. 문제를 처음 읽었을 때는 '딱 봐도 사이클 구하라는 거잔하... 예제를 이르케 뒤로만 가고 앞으로 가는 케이스를 안 준다고??ㅠㅠ' 이랬었다. 하지만 가만히 생각해보니 사이클을 구했다고 치자. 근데 10의 100승 번 움직이고 나서를 어떻게 구하지?? 나누기로 되나?? 이런 생각이 들었다.

 

10의 100승을 실제로 계산 때리라는건 아닐테고,, 무언가 숨겨진 조건이 있을 삘이었다. 그래서 문제를 자세히 읽어봤더니, i <= A_i <= N  이런 조건이 있었다. 애초에 말이 앞으로 갈 수가 없었던 것이다. 사이클 자체가 만들어지지 않으므로, 그냥 말의 진행방향의 역방향으로 탐색을 한 번 돌려주면 끝인 아주아주 간단한 문제였다.

import sys
input = sys.stdin.readline

# 입력 처리
n = int(input())
arr = [0] + list(map(int, input().split())) # 계산 편의성을 위해 맨 앞에 0 추가

# 역방향 탐색
for i in range(n, 0, -1) :
    # 최종 도착지 갱신
    if arr[i] != i :
        arr[i] = arr[arr[i]]

# 출력 처리
for i in range(1, n+1) :
    print(arr[i], end=' ')

 

뒤에서 부터 리스트를 탐색하며, 현재 칸이 최종 도착지가 아닐 경우에 현재 칸의 최종 도착지로 값을 갱신해 주었다. 이후 출력 처리를 해 주면 끝!

 

# D문제

https://atcoder.jp/contests/abc445/tasks/abc445_d

D - Reconstruct Chocolate

문제를 쭉~~ 읽고,, 아 그리디네^^;; 넘길까ㅎㅎ.. 이런 생각을 했따.

일단 매우 쫄음 상태로 접근을 시도했다. (그리디 싫어어어)

정답이 나올 수 있는 가짓수가 여러가지 였지만, 전체 초콜릿의 범위가 정해져 있기 때문에 결국 가장 큰 조각들을 먼저 붙이면 되지 않을까 싶었다. 

대충 정렬이 필요하고, 오름차순 정렬 했을 때 가장 맨 뒤에 있는 놈을 빼서 갖다 붙이면 될 것 같았다. 그럼 높이가 긴 조각을 먼저 붙여야 할까 너비가 긴 조각을 먼저 붙여야 할까? 여기에 아래 그림과 같은 케이스의 경우에는 붙이는 순서에 따라 남는 공간을 단순 계산으로 가늠하기 힘들어졌다.

 

2차원 배열을 써야 하는 건가?? 가만 생각해보니 조각의 길이가 아니라 넓이를 기준으로 붙여도 될 것 같았다. 이렇게 머리가 펑 터져버리고... 다음 문제로 대피했다. 그리고 탈탈 털린 후 다시 이 문제로 돌아왔다 ^^..

 

그리고 깨달음이 찾아왔다. 초콜릿을... 손으로 뽀개는 구나...!! 저 그림같은 케이스가 나올 수가 없는 거였어!! 게다가 무조건 최대 높이나 너비를 가진 초콜렛이 있을 수 밖에 없구나!! 아하!!!

이로서 모든 의문과 막히던 부분이 사라지고 문제를 풀 수 있었따.

import sys
input = sys.stdin.readline

# 입력 처리
h, w, n = map(int, input().split())
arr = [ list(map(int, input().split()))+[i] for i in range(n) ] # 삭제 연산을 위해 끝에 인덱스 번호 추가

# 정렬
h_arr = sorted(arr, key=lambda x: x[0]) # 높이 오름차순
w_arr = sorted(arr, key=lambda x: x[1]) # 너비 오름차순

# 변수 선언
curr_h = h    # 현재 채워야 할 남은 높이
curr_w = w    # 현재 채워야 할 남은 너비
curr_x = 1    # 현재 초콜렛을 놓을 x좌표
curr_y = 1    # 현재 초콜렛을 놓을 y좌표

visited = [False] * n    # 삭제 연산을 위한 방문 처리 리스트
answer = [ [0, 0] for _ in range(n) ] # 정답 저장 리스트: (x, y) 좌표들

# 초콜릿 조각 놓기
for _ in range(n) :
    # 삭제
    if h_arr and visited[h_arr[-1][2]] : # 너비가 가장 긴 초콜렛을 놓아서 높이 리스트에서 삭제가 필요한 경우
        h_arr.pop()
    if w_arr and visited[w_arr[-1][2]] : # 높이가 가장 긴 초콜렛을 놓아서 너비 리스트에서 삭제가 필요한 경우
        w_arr.pop()

    # 높이
    if h_arr and h_arr[-1][0] == curr_h : # 현재 채워야 할 높이와 일치하는 높이를 가진 조각이 있을 경우
        pop_h, pop_w, pop_i = h_arr.pop() # 삭제 연산
        visited[pop_i] = True             # 방문 처리
        answer[pop_i] = [curr_x, curr_y]  # 좌표 저장
        curr_w -= pop_w                   # 남은 너비 갱신(현재 채워야 할 높이와 일치하는 높이를 가지는 조각을 두었으므로, 높이는 조정되지 않음)
        curr_y += pop_w                   # y좌표 갱신(마찬가지로 x좌표는 조정되지 않음)
        
    # 너비
    else :                                # 높이와 방식 똑같음.
        pop_h, pop_w, pop_i = w_arr.pop()
        visited[pop_i] = True
        answer[pop_i] = [curr_x, curr_y]
        curr_h -= pop_h
        curr_x += pop_h

# 출력 처리
for i in range(n) :
    print(answer[i][0], answer[i][1])

 

꼼꼼히 빼먹는 것 없이 구현해 주면 된다. 삭제 조건 처리 과정에서 리스트가 비어 있을 것을 고려하지 못해서 인덱스 에러가 자꾸 났는데 무사히 시간 안에 해결했다. 깨달음이 뒤늦게 찾아와서 식은땀이 좀 났다. 마감 3분 전에 처음으로 제출해서 무사히 통과했다.

 

# E문제

https://atcoder.jp/contests/abc445/tasks/abc445_e

E - Many LCMs

처음에는 그냥 소수를 구하는 범위가 넓은 문제라고 생각했다. 근데 시간복잡도에서 걸려서 문제라 구현이 막혔다.

무식하게 n-1개 원소에 대한 최소공배수를 n번 구하면 시간이 아주그냥 시원하게 터져버린다.

수학을 잘하는 편이 아닌지라 30분 날려먹은 후 D번으로 돌아가고 다시 보지 못한 채 끝났다.

푸는 방법은 우선 에라토스테네스의 체를 이용해 가장 작은 소인수를 구하고, 모든 수를 소인수 분해 하며 정보를 업데이트 해 주면 된다. 각 소수가 각 숫자들에 몇 번씩 포함되어 있는지(=지수)를 리스트에 저장하고 가장 큰 값을 구해 최소공배수에 영향을 미치는 수를 구한다. 이후 Ak를 빼며, Ak가 가진 지수가 최대이라면 최소공배수에 영향을 미치던 수 이므로 두번째로 큰 수로 최소공배수를 구해주면 된다.

Ak를 제외하는 부분에서 막혀서 풀지 못한게 큰 것 같다. 좀 더 다양하게 알고리즘 문제를 풀어볼 필요가 있다고 생각했다.

 

# F문제

https://atcoder.jp/contests/abc445/tasks/abc445_f

F - Exactly K Steps 2

BFS나 다익스트라 문제 같지만 범위 제한을 보면 10억이다. 1억도 아니고 10억. E번 풀다가 때려치고 이 문제를 열람했다가 곧장 백스텝 밟고 D번으로 넘어갔다.. 푸는 방법은  (Min, +) 행렬 곱셈(Tropical Matrix Multiplication)을 이용한 고속 거듭제곱(Matrix Exponentiation) 알고리즘으로 해결해야 한다고 한다. 내가 이해하기엔 아직 너무 이른 영역이라 생각하기로 했다(ㅎㅎ..)

 

# G문제

읽어 보지도 못했다.

---

 

이렇게 4솔로 첫 엣코더 응시를 마무리했다. 그래도 절반은 풀었다는 사실에 의의를 두기로 했다.. E와 F 문제를 읽어봤을 때 아마도 당분간 4솔이 한계이지 않을까 싶었다. 이번엔 문제 운이 좀 좋았던 편인것 같다. 더 열심히 공부해야디... 백준 잔디밭을 푸릇푸릇하게 채울테야

 

시간 제한을 두고 문제를 풀어보니 색다른 느낌도 들었다. 오프라인 코테에 한 번 참여해 본 적이 있긴 하지만 정말 경험 삼아서 얼레벌레 간 거라 시간이 제한되어 있다는 느낌을 크게 받지 못했었다. 하지만 이번에 D번을 아슬아슬하게 제출하면서 이런 온라인 코테 응시 경험도 많은 도움이 될 수 있을거란 생각이 들었다. 아무튼 열심히 하면 좋은게 좋은거닷.