2019 KAPC 문제 풀이

작년 9월에 열렸던 우리 학교 대회 문제를 풀어 보았다. 사실 이거 보고 동아리 들어온건데, 당시 출제진 중 다수가 군대를 가는 바람에(ㅠㅠ) 올해는 안 열릴 것 같다.

 

그런데 왜 코틀린은 사용 불가능한 겁니까?

2019 건국대학교 동아리 알프스 프로그래밍 경진대회 (KAPC)

---

A. 타자 연습

왼손과 오른손이 키보드를 누르는 횟수의 차이를 최소로 만들어야 한다. 글자를 누르는 손은 정해져 있으니 Shift와 스페이스 바로 균형을 맞추면 된다. 각 손이 눌러야 하는 키 개수의 차이가 1일 때에는 왼손으로 한번 더 누른다는 점에 유의하자.

B. 수강 바구니

수강바구니(줄여서 수구니)는 수강신청할 과목을 미리 담아두면 인원이 초과되지 않은 강의는 자동으로 신청되는 제도이다. 다른 학교에도 이런 게 있는지는 모르겠지만 새내기때 수구니를 접하고 좋은 의미로 충격받았던 기억이 있다. 이게 대학의 일처리인가? 지금 보면 일처리가 아주 뛰어난 것 같지는 않지만..

 

뭐 어쨌든 문제의 조건대로 구현하면 된다. 실버5 치고는 빡센 조건이 아닌가 싶다.

C. 보물 찾기

나는 이런 류의 문제를 무한 DP라고 부른다. 상하좌우 4방향으로 모두 움직일 수 있기 때문에 bottom-up을 적용할 수 없기 때문이다.

 

그런데 DP 없이 그냥 dfs해도 된다. 각 칸을 방문할 때마다 visit 체크를 해 주고, 다음 글자를 주변 4방향 칸에서 찾아 움직이면 된다. 이때 이미 방문했던 칸을 다시 방문했다면 단어를 무한히 찾을 수 있다는 뜻이기 때문에 -1을 출력해야 한다. 칸을 방문한 후에는 visit을 다시 false로 돌려놔야 한다. 나중에 이 칸을 다른 경로로 방문할 수도 있기 때문이다.

 

맵이 커지면 DP를 써야 할 것 같다. 현재 칸으로부터 단어를 찾을 수 있는 최대 횟수를 저장하면 되지 않을까?

D. 일감호에 다리 놓기

일감호는 건대 부지의 중앙에 떡하니 있는 호수이다. 에타에 잊을 만 하면 '일감호에 대학을 넣어보자' 시리즈가 올라오는데, 외대는 확실히 들어갔던 걸로 기억한다.

크긴 크다

실제로 다리가 필요하긴 하다. 법학관~제2학생회관 경로가 괜찮은데 안전 문제랑 건설비용(호수 바닥이 뻘..) 때문에 아마 안 될 것 같다.

 

문제 자체는 어렵지 않다. 와우도와 각 강의동을 그래프로 이어 주고, 최소 스패닝 트리의 가중치가 k보다 작은지 비교하면 된다. MST를 아는 지 판단하려는 의도였던 것 같다.

E. 고양이 밥주기

전형적인 외판원 순회 문제이다. N이 최대 16이기 때문에 외판원 문제를 모르더라도 그냥 브루트 포스로 모든 순서를 따져보면 된다.

 

기껏 코드 짰더니 채점 준비중이어서 눈물.. 첫 대회라 그런지 데이터 검수가 미흡했나 보다.

F. 바둑알 점프

처음 봤을 땐 조금 어려워 보였는데, $3 \le N \le 10$을 보고 안심했다. 이 정도 크기면 아무리 단순하게 짜도 풀린다. 

 

문제의 조건을 브루트 포스로 빠짐없이 구현하기만 하면 된다. 각 바둑돌에 대해 점프할 수 있는 모든 방향으로 점프해 보자. 구현이 조금 귀찮을 수도 있지만 이 정도는 할 수 있어야 한다.

G. 동아리 홍보하기

전봇대에 동아리 홍보지를 붙이려고 하는데, 전봇대는 트리 형태의 길로 이어져 있으며 홍보지를 붙인 전봇대와 인접 전봇대에 홍보 효과가 나타난다. 모든 전봇대에 홍보 효과가 나타나도록 하려면 전단지를 최소 몇 장 붙여야 할까?

 

대회 문제 중 가장 까다롭다. 처음에는 최소 버텍스 커버인 줄 알았는데 아니었고, 트리 DP를 수행해야 하는데 DP의 상태를 정의하기가 어려웠다. 연속해서 전단지를 붙이지 않은 전봇대의 수를 사용해 봤는데 틀렸고.

 

60점을 받은 후 다른 분들의 코드를 참고하여 풀었다. 풀었다고 하기도 부끄럽지만 그래도 적어 본다.

 

상태는 다음과 같이 정의한다.

 

• 0: 이 노드가 선택됨
• 1: 이 노드가 선택되지 않았지만 인접한 노드가 선택됨
• 2: 이 노트가 선택되지 않았고 인접한 노드가 선택되지도 않음

각 상태에 따라 인접 노드가 가질 수 있는 상태를 이용하여 dp 배열을 채우면 된다.

H. 후임 간식 뺏어먹기

냅색 변형 문제이다. 주어진 포만감 이상으로 얻을 수 있는 만족도의 최솟값을 찾아야 하는데, 이분 탐색을 섞으면 되지 않을까? 이것도 채점 준비중이길래 깊게 생각해 보진 않았다.

I. 피아노 연주

보자마자 DP 문제라는 감이 와야 한다. 다음과 같이 dp를 정의한다.

 

$dp[i][l][r]$: 왼손이 $l$에 있고 오른손이 $r$에 있을 때, $i$부터 끝까지 치기 위해 움직여야 하는 위치의 최솟값

 

$i$번째 음을 $note[i]$라고 할 때, $dp[i][l][r]=\min(|note[i]-l| + dp[i+1][note[i]][r], |note[i]-r|+dp[i+1][l][note[i])$이다. 이때 문자로 주어지는 음을 수에 대응시켜야 한다. 나는 C0을 $0$으로 주고 반음마다 1씩 커지도록 수를 부여했다.

 

대회 때 솔브가 없었는데 다들 앞 문제 푸시느라 바쁘셨던 모양.