[Baekjoon Contest] 2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2022 Winter) Open Contest
| 2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 풀이 | ||
|---|---|---|
| A | [BOJ 24542] 튜터-튜티 관계의 수 | |
| C | [BOJ 24544] 카카오뷰 큐레이팅 효용성 분석 | |
| D | [BOJ 24545] Y | |
| G | [BOJ 24548] 도로 정보 | |
| K | [BOJ 24552] 올바른 괄호 | |
| L | [BOJ 24553] 팰린드롬 게임 |
1. 대회 후기
2022/02/27 백준 내부 대회 ‘2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2022 Winter) Open Contest’에 참가했다.
전체적으로 문제들의 난이도가 상당했고, 난이도순 문제 배열이 아니라 더 복잡하게 느껴졌다. 덕분에 $A$번에 쉬운 문제가 나올 줄 알고 가볍게 풀기 시작했다가 생각보다 어려워서 매우 당황하였다.
$A,C,D,K,L$ 총 다섯 문제를 풀었고, $G$랑 $J$정도가 못 푼 것이 아쉬운 문제였다. 나중에 풀 수 있으면 풀어보려고 한다.
2. 공식 풀이 링크
공식 풀이의 링크는 아래에 걸어두었다.
3. 문제 풀이 및 후기
A. 튜터-튜티 관계의 수 (7분)
문제의 핵심을 숨기기 위해 글을 굉장히 어렵게 서술해놓았다. 결론은 여러 개의 트리가 주어지면(이 트리들 전체가 하나의 그래프가 된다), 각각의 트리의 노드 수의 곱을 구하는 문제이다.
인원수가 최소가 되면서 모든 자료가 전달되기 위해서는 (하나의 트리에서) 하나의 시작 지점을 정하고 그 지점에서 연결된 모든 노드로 퍼져 나가야 하기 때문이다.
하나의 트리에서 시작 지점을 정하는 경우의 수는 그 트리의 노드 개수이고, 각각의 트리에서 시작지점을 하나씩 고르는 작업이기 때문에 곱하는 것이다.
C. 카카오뷰 큐레이팅 효용성 분석 (3분)
$A$번이 아니라 $C$번에 위치해 있는 문제라는 점 빼고는 신경 쓸 점이 없다. $A$번을 풀고 난 후여서 초반부 글이 의미 없다는 점을 파악하고 바로 후반만 빠르게 읽고 풀었다. 문제 그대로 전체 합과 등록되어 있지 않은 것들의 합을 구하면 된다.
D. Y (36분)
하나의 노드에서 세 방향으로 일자로 쭉 뻗은 삼발이(?) 형태의 그래프가 Y-트리이다. (말 그대로 Y 모양 트리)
처음에는 주어진 트리에서 정점을 제거해서 Y-트리를 만들고자 했다. $A$번 문제처럼 tree dp로 생각해보았는데 마땅한 방법이 떠오르지 않았다.
여러 예시를 만들어 보던 중, 최소의 정점을 삭제하게 되면 남는 Y-트리의 팔 길이가 길어야 한다는 사실을 알게 되었고 여기서 힌트를 얻을 수 있었다.
Y-트리의 두 개의 팔만 생각해보면, 예전에 백준에서 풀었던 문제 유형 중 하나인 트리의 지름이 떠올랐다. 트리의 지름은 그 트리에서 제일 긴 길이이기 때문에 트리의 두 팔을 만족한다.
이제 나머지 한 팔만 찾으면 된다. 이는 트리 지름 경로에서 임의의 정점을 잡았을 때, 해당 정점에서 뻗어 나간 길이가 가장 긴 정점을 찾으면 된다. 이렇게 세 개의 팔을 완성할 수 있다. (몇 개를 제거하는가 보다는 완성된 형태가 어떤 형태인가에 주목해야 했다.)
G. 도로 정보 (non-contest)
$3$의 배수 개수만큼 있어야 하기 때문에, 누적합을 $3$으로 나눈 값이 동일하면 된다. 따라서 $dp[3][3][3][3]$을 만들고 여기에 개수를 누적시키면, 새로운 index에 도달했을 때 그 위치의 dp만큼 새로운 흥미로운 구간을 만들 수 있어 이를 더해주기만 하면 된다.
K. 올바른 괄호 (33분)
정말 어려웠는데 $28$일 기준 백준 난이도로 실버$1$이어서 굉장히 당황스러운 문제 중 하나이다. 뭔가 훨씬 더 쉬운 방법이 있을 수도 있겠다는 생각이 들었다.
올바른 괄호열이 되는 문자가 존재하기 때문에 경우의 수는 총 두 가지이다. (가 하나 더 많거나, )가 하나 더 많거나.
)가 하나 더 많은 경우를 기준으로 생각해 보았을 때, 처음으로 )가 하나 더 많아지는 구간까지 나오는 )만 변경 가능하다.
)가 하나 더 많아지는 구간을 $x$라 가정하고 얘기해보면, $x$ 이전 구간($x$ 포함)은 (와 ) 개수가 동일한 괄호열이다. 여기서 )를 하나 제거하게 되면, )가 하나 부족한 괄호열이 되고 $x$에서 ) 하나가 채워져서 올바른 괄호열이 완성된다.
x 이후 구간 또한 (와 ) 개수가 동일한 괄호열이다. 여기서 )를 하나 제거하게 되면 )가 하나 부족한 괄호열이 되고 이는 $x$ 이후 구간이기 때문에 개수를 동일하게 맞춰줄 수 없다. 따라서 처음으로 )가 하나 더 많아지는 구간까지 변경 가능한 것이다.
(가 하나 더 많은 경우는 문자열 전체를 뒤집어 버리면, 위의 )가 하나 더 많은 경우로 바꿔버리고 위 방법을 적용시킬 수 있다. 문자열 전체를 뒤집다는 것은 좌우 방향으로 flip해버림을 의미한다. $ ‘()((())’ \rightarrow ‘(()))()’ $
L. 팰린드롬 게임 (10분)
백준에 있는 돌 가져가기 게임이어서 dp일 것이라 예상했지만, $N\leq 10^{18}$ 범위를 보고 그리디한 방법이 존재함을 깨달았다.
$N=1, N=2, N=3$일 때를 직접 전부 써보았다. $N=1\sim 9$는 팰린드롬 수이기 때문에 상윤이 이긴다. $N=10$은 $10$을 한 번에 가져갈 방법이 없어서 승우가 이긴다.
$N=11\sim 19$는 상윤이 $1\sim 9$를 가져가서 승우 차례에 돌이 $10$개 남게 만들면, 승우를 지게 만들 수 있어 상윤이 이긴다. 이런 식으로 계속 이어가게 되면, $10, 20, 30, 40,…$ 일 때 승우가 이기는 것을 알 수 있다.
이걸 깨닫고 세 자리 수도 계산해 보았는데 똑같이 $10$의 배수이면 승우가 이기는 양상을 확인할 수 있었다. 그냥 $1\sim 9$를 가져갈 수 있으니까 그런가보다 싶긴 한데 왜 팰린드롬 수가 이런 결과를 만들어 내는지에 대해서는 잘 모르겠다.
이정도로 분석하고 나머지 수에서도 똑같을 것 같아서 $10$의 배수이면 승우가 이기는 것으로 하고 제출해서 맞았다. 정확한 증명은 못하겠다.
댓글남기기