[백준] 2023 SCON Open Contest 후기

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

2023 SCON Open Contest

[총평]

(일주일이나 지나서 기억이 가물가물..하긴 하지만 아무튼..)
대학교 학사일정이나 다른 외부대회 일정상 5월만큼 대학교 교내 대회를 열기 좋은 달은 없는 것 같다. 그래서 그런지 5월에 대회가 쏟아져 나오고 있다.

2019 SCON이 숭실대학교의 가장 최근 대회인 것으로 보아 숭실대학교 대회가 오랜만에 열린 것 같다. ICPC에서 좋은 성적을 내는 대학으로 잘 알고 있기 때문에 개인적으로 많은 기대가 됐었다. 기대만큼 문제도 재미있었고 기발하지 않았나 하는 생각이 들었다. 적절한 난이도 커브는 덤.

D번에서 배열 크기를 잘못 잡은 어이없은 실수와 E번에서의 삽질만 빼면, 내가 할 수 있는 건 최대한 하지 않았나 싶다. H번과 I번의 난이도가 오락가락하다가 H번의 난이도에 플레5가 찍히면서, 대회 중 골드 문제는 다 풀자는 목표를 달성..하게 되었다. I번은 홀수 길이 사이클로 어찌저찌 비벼보면 될 것 같은데.. 모르겠다. 나중에 다시 한 번 봐야겠다.

[문제 풀이]
A번. 정보섬의 대중교통

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

28113번: 정보섬의 대중교통

간단한 사칙연산. 버스를 타려면 $A$분이, 지하철을 $B$분이 걸리므로 그 두 값을 비교한다. 단, 지하철을 타기 위해서는 $N$이 $B$보다 작아야 함을 유념해야 한다.

B번. 팀명 정하기

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

28114번: 팀명 정하기

비교해야 하는 대상이 3개 밖에 없으므로 단순 비교도 가능하다. 그래도 커스텀 정렬 두 번(한 번은 입학 연도 기준, 한 번은 해결 문제 수 기준으로.) 하는 쪽이 구현도 쉽고 정신 건강에 이롭다.

181920, NLP.. 너무나도 유명한 팀 이름이다. 경희대에서도 그런 팀이 나왔으면 좋겠다.

C번. 등차수열의 합

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

28115번: 등차수열의 합

어떤 수열 $B$, $C$가 등차수열일 때, 각각의 초항과 공차를 ($b$, $d_1$), ($c$, $d_2$)라 하자. 이때 두 수열을 합할 경우 $b+c$, $(b+c) + (d_1+d_2)$, $(b+c) + 2(d_1+d_2)$와 같이 이어지고, 이 또한 등차수열임을 알 수 있다. 따라서 수열 $A$가 등차수열이어야 YES를 출력할 수 있다.

최근에 구데기컵에 출제됐던 27907번(The primes contain arbitrarily long arithmetic progressions)의 공차 0 트릭(?) 덕분에 해 구성하기는 어렵지 않게 해결할 수 있다. 다른 사람들도 비슷하게 생각했던 듯 싶다.

D번. 선택 정렬의 이동 거리

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

28116번: 선택 정렬의 이동 거리

어떤 어려운 트릭이나 알고리즘 없이 단순 구현만으로 풀 수 있는 문제. 그럼에도 문제가 되는 건 그 구현 난이도..가 아닐까 싶다. 자칫 잘못하면 그대로 꼬여버려서 폭사할 수 있다.

주어진 수열에서 1부터 $N$까지의 수가 한 번씩 등장하므로 수를 입력받을 때마다, 그 수의 위치를 배열로 저장해놓는다. 이 배열을 idx라 하자. idx 배열을 1부터 $N$까지 돌면서, 이동 거리를 계산한다. 어떤 수의 이동 거리는 그 수의 원래 위치와 현재 위치의 차의 절대값이다. 이 이동 거리를, 교환해야 하는 수에도 똑같이 적용한다. 이후 실제로 그 두 수를 swap을 통해 바꿔 놓는다. 이를 반복.

E번. prlong longf

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

28117번: prlong longf

조합론 문제는 늘 까다로운 것 같다.. 여러 실수 덕분에 4번 만에 맞춘 문제.

문자열을 처음부터 돌면서 long이 서로 붙어있는 덩어리들을 탐색한다. 우선 덩어리 내에서의 경우의 수를 살펴보자. longlonglonglong일 경우 longlonglonglong, longlonglonglong, longlonglonglong, longlonglonglong, longlonglonglong으로 총 5가지 경우이다. 이는 어떻게 계산할 수 있을까?

long 개수를 늘려가며 끄적거리다 보면 이는 피보니치 수와 깊은 연관이 있음을 알 수 있다. 어떤 덩어리의 long개수가 $k$개라고 하자. 맨 앞쪽의 long이 변환되지 않는 long이라면 이 경우의 수는 $k-1$개일 때와 동일하다. 반면 변환되는 long이라면 앞쪽 두 개의 long이 변환되므로 이 경우의 수는 $k-2$개일 때와 동일하다. 따라서 점화식은 $dp[i] = dp[i-1] + dp[i-2]$이다.

각각의 덩어리의 경우의 수를 구해놓고, 그 경우의 수들을 모두 곱해주면 된다.

F번. 안전한 건설 계획

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

28118번: 안전한 건설 계획

예시 몇 개를 끄적거리다 보면 문제 해결의 실마리를 발견할 수 있다.

굳이 유니온 파인드를 쓸 필요까진 없고, 그래프의 컴포넌트 개수만 세 주면 된다. 어떤 세 점이 같은 컴포넌트에 속한다면 항상 두 번째 작업이나 세 번째 작업만을 수행하게 된다. 반면, 어떤 두 기둥(같은 컴포넌트에 속해 있다.)과 다른 한 기둥이 각각 다른 컴포넌트에 속한다면 항상 첫 번째 작업만을 수행할 수밖에 없음을 보일 수 있다. 따라서 정답은 "컴포넌트의 개수 - 1"이 된다. 물론 이 풀이가 가능한 이유는 "서로 다른 두 기둥을 연결하는 빔이 항상 존재하도록 보강 작업을 진행할 수 있음이 보장된다"는 문제의 제한 덕분이다.

G번. Traveling SCCC President

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

28119번: Traveling SCCC President

개인적으로 기발하다고 생각하는 문제. 스코어보드를 봤을 때 꽤 풀린 것을 보고, 이 문제는 해볼만 할 것이라는 믿음을 가지고 접근했었다.

회의를 차례대로 진행해야 한다는 문구보다는 순간이동을 할 수 있다는 문구에 더 집중을 했어야 한다. 일단 모든 건물에 도달한 다음, 계속 순간이동을 한다고 생각해보자. 그렇게 되면, 이 문제는 바로 MST를 구하는 문제로 바뀌게 된다. 프림 알고리즘을 떠올려 보자. 이미 탐색한 정점에서 뻗어나갈 수 있는 간선을 탐색하는데, 이는 순간이동을 이용해 어디서든 다음 경로로 뻗어나가는 것과 유사하다고 볼 수 있다. (프림 알고리즘은 문제 접근을 용이하게 하기 위해서 가져온 것으로, 문제 해결은 당연히 크루스칼 알고리즘으로도 할 수 있다.)

[업솔빙]

(추후 추가 예정)