[PS] 2021 SNUPC Division 2

시작하기 전에...

이번에는 서울대학교에서 2021년 개최한 프로그래밍 경시대회 기출문제를 풀어보았다. Division 1과 2로 구분되어 있길래 난이도를 확인해보니 1은 문제부터가 감히 손도 못댈 것처럼 무시무시해보였고, 2는 그나마 풀어볼만 한 것 같아서 한 번 시도해보았다.

문제는 A~I까지 총 9문제로 구성되어있으며, 원래는 9문제를 다 풀고 글을 쓰려고 했으나 마지막 H, I 2문제가 너무 오래걸릴 것 같아서 푼 7문제부터 정리해서 올리려고 한다.

문제 풀이

A. 23037: 5의 수난

[링크] 단순한 구현 문제였다. cmath 헤더의 pow 함수를 사용했다.

B. 23038: 박스 그림 문자

[링크] 역시 단순한 문제였다. $i+j$가 홀수 일 때만 채우면 되기 때문에 상, 하, 좌, 우 모양이 채워져 있고 따라서 빈 칸의 모양이 유일하게 결정된다.
좀 더 고민했으면 훨씬 깔끔하게 짤 수 있었을 것도 같지만 우선 직관적으로 해결했다.

C. 23039: 실 전화기

[링크] 처음에 살짝 헤맸던 문제다. 뭔가 일반화 할 수 있을 것이라 생각하고 토끼가 3마리일 때부터 규칙성을 찾으려고 했는데, 그럴 필요 없이 토끼를 5마리로 고정하고 단순히 충돌이 몇개 생기는지만 확인하면 되는 문제였다.

실의 충돌이 1~4개 있을 때는 모두 하나의 토끼에서 나온 줄이 충돌한 것으로 볼 수 있고, 다행히 어떤 경우에서도 그 토끼만을 옮겨서 충돌을 없앨 수 있다.
문제는 충돌이 5개 있을 때인데, 완전그래프인 경우 절대로 충돌을 피할 수 없지만, 그렇지 않은 경우는 2개의 토끼를 옮겨서 해결할 수 있기 때문에 그 부분도 코드에 추가해주었다.

D. 23040: 누텔라 트리(Easy)

[링크] 그래프 문제를 안 풀었던 걸 후회하게 만들어준 문제였다. 막상 해설을 보고 곰곰이 생각해보니 생각 못할 것도 아니었는데, 지레 겁먹고 계속 어렵게만 생각했던 것 같다.

처음에는 DFS로 풀려고 했었다. 검은색 Node부터 시작해서 빨간색 노드를 탐색해나가며 count를 1씩 늘려가면 답이 바로 나오기 때문이다. 하지만 이렇게 풀 경우 검은색 노드가 많아졌을 때 걸리는 시간이 점점 늘어나고, 시간초과가 나게 된다.

그렇다면 어떻게 접근해야 할까? 출발하는 검은색 노드가 바뀌더라도 (검은색 노드가 없는) 연결된 빨간색 노드들의 집합은 변하지 않는다. 또한, 결국 누텔라 경로의 갯수는 그 집합의 빨간색 노드의 개수와 같기 때문에 메모이제이션을 이용해서 미리 계산해놓으면 시간초과를 막을 수 있다.

여러가지 방법으로 구현할 수 있겠지만, 나는 스택을 이용해서 해결했다.

E. 23041: 뛰는 기물

[링크] 이 문제도 굉장히 흥미로운 문제였다. 처음에는 "$(N,M)$-기물을 이용해서 $(0,0)$에서 $(p,0)$을 갈 수 있는가?" 에 관해서만 주목했었다. 그래서 $p = gcd(n+m, n-m)$일 때 $p^2$를 답으로 내려고 했었는데, 생각해보니 $(1,1)$로 갈 수 있는 기물의 경우 답이 $2$가 될 수 있었다. 그래서 $gcd(n,m)$으로 $p^2/2$가 나누어떨어질 경우에는 $p^2/2$을 답으로 내놓게 하였고, 정답을 맞힐 수 있었다.

하지만 이렇게 풀고 보니, 뭔가 수학적으로 증명할 수도 없고 찜찜한 마음이 들어 SNUPC 2021 공식해설 유튜브를 확인해보니 엄청난 일반화로 풀 수 있다는 사실을 알게 되었다... 이 부분에 대해서는 나중에 한 번 더 짚고 넘어가야 할 것 같다.

결국에는 운이 좋아서 맞췄던 걸로ㅠㅠ

F. 23042: AND와 OR

[링크] 이런 문제는 어떻게 생각하는건지 참 대단하다는 생각이 들었다. 이 문제에서 가장 중요한건

두 수를 고르고, 이 두 수를 두 수와 bitwise AND 및 bitwise OR가 모두 같은 두 음이 아닌 정수로 바꿉니다.

이 문장이었다. 그러면 다음과 같은 사실을 알 수 있는데,

1. AND와 OR이 같은 두 정수라고 한다면 두 정수의 이진법 상 같은 자리를 차지하는 비트가 다를 때 그 순서를 바꾸는 연산이라고 볼 수 있다.
2. 두 양수 $a, b (a>b)$가 있을때, $a$보다 작은 임의의 양수 $c$에 대하여 $ab > (a+c)(b-c)$임은 쉽게 증명 가능하다. 따라서 어떠한 연산을 하든지 주어진 수들의 곱을 최소화한다면 큰 수를 더 크게, 작은 수를 더 작게 만들어야 한다는 사실을 알 수 있다.

위의 두 사실로 부터, 문제에서 주어진 $N$개의 정수들의 이진법의 각 자릿수 별로 1의 개수를 센 뒤, 가장 큰 수부터 차례로 그 1을 넣어주면 해결할 수 있는 문제였다.

G. 23048: 자연수 색칠하기

[링크] 단순히 소수의 개수를 찾는 문제와 다를게 없다. 다만 소수 판별을 하다가 나누어 떨어지는 수가 발견되면 그 수와 같은 색으로 칠해주는 코드를 추가해주어야했다.

코드

위 문제를 푼 코드는 Github에 올려두었다.
https://github.com/brighthonor/PS/tree/master/SNUCP/2021_Div2

정리

몇 문제들은 자신있게 풀 수 있었지만, D나 E같은 문제들은 시간도 오래걸렸을 뿐만 아니라 수학적으로도 완벽히 증명하지 못하고 푼 것 같아 아쉬웠다. 그래프나 정수론 관련 문제들을 좀 더 많이 풀어서 익숙해져야 될 것 같다.

또, 글을 쓰면서 느낀거지만 내가 아는 것과 남에게 설명하는 것은 정말 큰 차이가 있다는 사실을 다시 한 번 깨달았다. 나름 열심히 설명한다고 쓴건데, 읽는 입장에서는 전혀 이해가 안 될 것 같아서 걱정이다. 지금부터라도 이해된 내용을 설명하는 연습을 계속 해나가야 할 것 같다.