[백준] 2023 부산대학교 CodeRace Open Contest 후기

 https://www.acmicpc.net/contest/view/994

2023 부산대학교 CodeRace Open Contest

4솔 마무리

폰에 컴파일러 앱을 깔아 둔 덕분에 컴파일 에러나 런타임 에러가 나올 일이 거의 없어졌다. 예제도 돌려볼 수 있어서 어이없게 틀리거나 하는 일이 없게 된 것도 좋은 것 같다.

대회는 총 4시간이었는데, 4시간을 온전히 쏟아붓진 않았다. C번을 2틀하고 난 후에는 내 능력으로 풀 수 있는 문제가 없다고 판단되어 대회를 일찍 종료했다.

[총평]

가장 아쉬운 점은 A번 삽질. 꼬아서 생각할 것도 없고 문제에서 요구하는 그대로를 했으면 됐는데, 혼자 어렵게 생각하는 바람에 시간을 많이 낭비했다. 쉬운 문제를 계속해서 틀리니 당황해서 조급해진 마음은 덤. 역시 대회는 멘탈 관리가 중요한 듯 싶다.

F번이 현재 시점에서 골드1 ~ 플레5를 왔다갔다 하는 것 같다. 골드급 문제를 다 풀었다면 5솔~6솔이었을 텐데 그러지 못한 점도 아쉽다. 대회에서 골드급 문제는 다 밀어보는 것을 목표로 더 열심히 해야겠다.

[문제 풀이]
A번. 첨탑 밀어서 부수기

https://www.acmicpc.net/problem/28014

28014번: 첨탑 밀어서 부수기

스택을 써야 될 것 같이 생겼지만 스택이 필요하진 않다. 이전 첨탑의 높이를 저장하는 변수 하나만 있어도 충분하다.

첨탑을 미는 횟수를 카운트할 때는 1. 처음 첨탑을 밀 때 / 2. 이전 첨탑의 높이보다 현재 첨탑의 높이가 크거나 같을 때 / 이다.

여담으로, 무슨 생각에 빠진 건지 모르겠지만, 내 첫 번째 접근은 lis였다..

B번. 영역 색칠

https://www.acmicpc.net/problem/28015

28015번: 영역 색칠

덧칠이 가능함에 주의. 1이던 2이던 간에 상관없이 색깔이 연속해서 칠해져 있는 모눈종이에 주목하자. 1 또는 2로 그 모눈종이를 한 번에 다 칠한 다음, (필요하다면) 아까 칠하지 않은 색으로 그 위에 덧칠하면 된다.

이때 그 색은 어떻게 정하는 것이 좋을까? 1이 연속으로 칠해져 있는 뭉텅이의 개수(one이라고 하자.)와 2가 연속으로 칠해져 있는 뭉텅이의 개수(two라고 하자.)를 비교한다. 예를 들어, 1 1 2 2 1과 같은 모눈종이가 있을 때 one = 2이고, two = 1이다.  min(one, two) + 1을 계속해서 합한다. 0을 만나거나 행이 바뀔 때마다 one, two를 0으로 초기화해주어야 한다.

이러한 덧칠 방법이, 뭉텅이를 만날 때마다 정직하게 하나하나 칠하는 방법보다 붓칠 횟수가 더 적다는 것은 증명하기 쉽다. one과 two 둘 중 하나는 최소 1이어야 하므로 one + two $\leq$ min(one, two) + 1이 성립한다.

D번. 게임을 클리어하자

https://www.acmicpc.net/problem/28017

28017번: 게임을 클리어하자

DP 연습이 빛을 발했던 문제. 소소하지만 이번 대회 중 제일 뿌듯했던 경험이었다.

dp 식을 다음과 같이 정의해보자.
$dp[i][j] =$ 지금이 $i$회차이고, 이전 회차에서 사용한 무기가 $j$번 무기일 때, 앞으로의 총 클리어 시간의 최솟값

1번 무기부터 $n$번 무기까지를 돌면서 이번 회차의 무기를 선택한다. 물론 이전 회차에 골랐던 무기 번호를 골라선 안 된다. 다음 회차에는 이번에 골랐던 무기를 고르면 안 되므로 dp식은 다음과 같이 전개된다.

$dp[i][j] = (dp[i+1][k] + \textrm{weapon}[i][k])$ 중 최솟값
이때 $k$는 1부터 $n$까지 중 $j$가 아닌 수이다.

E번. 시간이 겹칠까?

https://www.acmicpc.net/problem/28018

28018번: 시간이 겹칠까?

A번에서의 숱한 삽질 덕분에 이 대회에서 가장 처음 푼 문제. 2021 카카오 블라인드 채용 코딩테스트에 나왔던 [광고 삽입] 문제(https://school.programmers.co.kr/learn/courses/30/lessons/72414)가 떠올라 거기서 사용했던 테크닉을 이용하였다.

$S$에서 $E$까지를 일일이 $N$번 체크하는 나이브한 방법으로는 시간초과가 걸린다. 나이브한 방법에서 누적합을 섞어 한 발자국 더 나아가보자. 시간을 나타내는 임의의 배열에 어떤 시작점 $S$에는 1을 더하고 끝점 $E+1$에는 1을 뺀다. 시간 배열의 앞에서부터 누적합을 할 경우 최종 시간 배열은 나이브한 방법과 같아진다. 이를 이용하면 시간복잡도 $O(N)$으로 문제를 해결할 수 있다.

[업솔빙]

(추후 추가 예정)