[Baekjoon Contest] 2022 숭고한 연합 알고리즘 콘테스트 Open Contest
| 2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이 | ||
|---|---|---|
| A | [BOJ 24883] 자동완성 | |
| B | [BOJ 24884] 장작 넣기 | |
| C | [BOJ 24885] 주식 | |
| D | [BOJ 24886] SKH 문자열 | |
| E | [BOJ 24887] 최대한의 휴식 | |
| F | [BOJ 24888] 노트 조각 | |
| I | [BOJ 24891] 단어 마방진 |
1. 대회 후기
(문제들이 division 3,2,1로 나뉘어있다.)
2022/03/27 백준 내부 대회 ‘2022 숭고한 연합 알고리즘 콘테스트 Open Contest’에 참가했다. 풀만한 문제가 꽤 많았음에도 불구하고, 한발자국을 더 딛지 못해 정답에 다다르지 못한 경우가 많아서 아쉬웠다. D, E, F가 전부 그랬다.
B, C 같은 경우도 문제의 지문 또는 핵심을 제대로 파악하지 못해서 엉뚱하게 구현하는 바람에, 코드를 갈아엎는 과정에서 시간을 너무 많이 잡아먹었다. 문제를 제대로 읽고 어떻게 코딩해야 할지 대략적인 개요를 짠 후에 코딩하는 습관을 제대로 길러야 겠다고 생각했다.
2. 공식 풀이 링크
공식 풀이는 ‘백준 > 게시판 > 홍보 > 2022 숭고한 연합 알고리즘 대회 종료’의 2022-skh-solution.pdf 파일을 통해 알 수 있다. 대회의 풀이 파일들이 주로 이곳에 게시된다. 해당 링크를 아래에 걸어두었다.
3. 문제 풀이 및 후기
A. 자동완성 (1분)
실제 대회에서 $A$번에 이런 긴장을 풀어주는 문제가 있으면 굉장히 도움될 것 같다. 그냥 $if$문에 따라 다른 출력을 다루는 문제였다.
B. 장작 넣기 (40분, WA: 1)
각 단계마다 취할 수 있는 행동은 총 세 가지가 있고, $N$의 최댓값이 $6$이기 때문에 $3^6=729$여서 브루트포스를 돌리기에 충분하다. 따라서 모든 경우의 수를 탐색하도록 구현하였다.
막상 지금와서 완성 코드를 보면 그렇게 오래 걸릴만한 게 없는 것 같은데, 제대로 로드맵을 정해놓지 않고 코딩하다보니 여기저기서 헤맸던 것 같다. 앞으로 코딩하기 전에 어떻게 구현할지를 좀더 확실하게 정하는 습관을 들여야겠다.
구현 상으로 $T$시간일 때, $F$의 값을 제대로 되돌리지 못하는 문제가 발생했다. 이 때문에 WA를 한 번 받았고, 해당 문제점을 발견하는데도 상당히 오랜 시간이 소모되었다.
C. 주식 (59분, WA: 1)
각 단계마다 취할 수 있는 행동이 총 네 가지가 있고(매도를 할지말지 * 매수를 할지말지) $N$의 최댓값이 $10$이기 때문에 $4^{10}\fallingdotseq 1,000,000$여서 브루트포스를 돌리기에 충분하다. 따라서 $B$번과 마찬가지로 모든 경우의 수를 탐색하면 된다.
상당히 복잡해 보이는 문제였으나, 곧이곧대로 구현하면 생각보다 쉽게 할 수 있을 것 같아서 $B$번 다음으로 바로 도전하였다. 매도를 할지말지 정하고 매수를 할지말지 정하는 것에 따라 총 네 가지 경우가 나오고, 이 모든 경우를 구분하여 구현하였다.
애초에 문제 해석을 잘못해서 원래 의도와는 다르게 엄청 돌아갔다. 대출 제한이 $K$라는 것을, 대출 횟수 제한이 $K$라고 잘못 이해해버린 것이다. 덕분에 $K$값을 줄어들게 만들고 $K$번 대출하면 더이상 대출 못하게 만드는 식으로 잘못 구현하여, 예시 1번의 정답이 계속 나오지를 않았다. 대략 30분의 디버깅 끝에 문제를 잘못 읽었음을 알 수 있었다.
$K$값을 고정시키고 대출을 무제한 가능하게 만드는 식으로 바꾸고 나서 제출했더니 WA를 받았다. 하도 문제가 복잡하다보니 당연히 구현상의 실수일것이라 생각해서 오류를 찾아 한참을 헤맸다.
나중에서야 특정 경우에 돈이 엄청나게 불어난다는 사실을 깨닫고, long long 자료형을 안 써서 WA를 받았음을 알 수 있었다. int를 초과하는지 안하는지는 아래 예시를 통해서 확인해 보았었다.
$N=10, M=1000, K=4$
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| P[i] | 100 | 1000 | 100 | 1000 | 100 | 1000 | 100 | 1000 | 100 | 1000 |
| 매도 | X | O | X | O | X | O | X | O | X | O |
| 매수 | O | X | O | X | O | X | O | X | O | X |
D. SKH 문자열 (non-contest)
$SKH$문자열의 개수를 세서 제외하고, $SK, KH, SH$ 문자열의 개수를 세서 각각 $H, S, K$를 사용하여 만들고, 남는 $S, K, H$에 각각 $KH, SH, SK$를 사용하여 만들고, 남는 것들로 $SKH$를 만드는 방식으로 코딩하면 될 줄 알았다. 그런데 남는 $S, K, H$에 $KH, SH, SK$를 최적으로 배정하는 방법에서 막혔다. 도저히 모르겠어서 대회에서는 풀기를 포기했다.
나중에 대회 풀이 슬라이드를 보고, $KH, SK, SH$를 붙이는 방식이 모든 경우의 수를 가정해서 푼다는 사실을 알게 되었다. $S$에 $KH$를 최대 $x$개만큼 붙일 수 있다면, $0$개부터 $x$개까지 모두 붙여봐서 각각에서 $SK, SH$를 붙여서 최댓값을 갱신하는 방식이었다.
방법을 알아도 구현이 조금 까다로워서 WA도 몇 번 받았다. 이런 방식의 완전탐색일줄은 상상도 못했고, 새로운 해결 방법을 하나 알게 되었다.
E. 최대한의 휴식 (non-contest)
비슷한 유형이 많은 이분탐색 문제로 보였다. 간격을 $1$부터 $N-1$로 설정하고 이를 left, right로 설정하여 이분탐색을 돌렸다. 그런데 길이가 간격으로 딱 나누어 떨어지지 않는 경우, 최적의 수를 선택하여 합의 최댓값을 찾는 방법에서 막혔다. 모르겠어서 대회에서는 풀기를 포기했다.
대회 종료 후, 알고리즘 분류에 dp가 써있는 것을 보고 dp를 포함시켜 생각해보았다. 그리고 이분탐색을 해서 mid값이 정해지면 이를 토대로 dp를 수행하여, 간격이 mid 이상이면서 수를 여러 개 골랐을 때 최대 합을 구할 수 있다. 여기에 설명하면 너무 길어져서, 자세한 설명은 아래 상세 풀이 링크를 따라가면 볼 수 있다.
요새 dp문제를 많이 안풀어서 감이 좀 떨어진 것 같다. 다른 알고리즘과 dp를 융합하여 푸는 연습도 많이 해보아야겠다. 또한, dp문제의 가장 큰 문제는 역시 문제를 보고도 dp문제인지 모른다는 것이다. 이를 위해 어느 상황에서 dp를 써야 하는지 최대한 분석해볼 것이다.
F. 노트 조각 (non-contest)
노트조각을 일일이 줍는 것을 기준으로 생각하면 너무 복잡하다고 생각했다. 그러다가 상대는 최적으로 달리고 내가 그 사람을 이기거나 비기려면, 무조건 최적의 경로로 이동해야 한다는 사실을 깨달았다. 그래서 최적의 경로를 전부 찾고 여기서 모든 노트 조각을 줍는 경우가 있다면, 그것을 정답으로 간주하면 될 것 같았다. 그런데 모든 최적의 경로를 효율적으로 찾는 방법을 모르겠어서 대회에서는 풀기를 포기했다.
대회 종료 후, 다익스트라 알고리즘을 돌리면서 생성한 Dist 배열을 바탕으로 백트래킹을 돌리며 모든 최단 경로를 확인할 수 있었다. 이전 대회에서도 백트래킹 문제를 못풀었었는데, 아직도 제대로 학습이 되지 않았나보다. 부족한 점을 확실히 알았으니, 이 부분을 보완하기 위해 노력해야겠다.
I. 단어 마방진 (27분)
문자열의 개수는 20개이지만, 선택하는 문자열의 개수는 5개이다. DFS를 돌릴 때 20개 중 5개를 고르려면, 총 $20^5=3,200,000$번의 탐색이 수행된다. 여기에 각각의 경우마다 단어 마방진인지 확인하므로 $5\times 5$만큼 탐색한다. 따라서 총 탐색은 $3,200,000\times 25=80,000,000$번이므로, 브루트포스를 돌리기에 충분하다.
사전순으로 제일 작은 정답을 출력해야 하므로, 처음에 문자열을 정렬한다. 그리고 DFS로 탐색하면서 답을 발견하는 즉시 그것을 답으로 간주하였다. 단어 마방진 확인은 위오른쪽에서 아래왼쪽 대각선으로 보았을 때, 모든 글자가 대칭인지 확인하는 방식으로 코딩했다.
댓글남기기