AtCoder Beginner Contest 160 회고

AtCoder Beginner Contest 160

AtCoder Beginner Contest 160 - AtCoder

오랜만에 AtCoder 포스팅으로 돌아왔습니다! 이마트에서 참치 세일을 한다길래 가봤는데 냉동참치더라구요. 냉동참치 200g에 12000원이라 그냥 야간 세일하는 초밥만 들고 집에 돌아왔습니다. 원래 AtCoder 시작 시간은 21:00이었구요 저는 22:00부터 시작해 40분동안 20분동안 A~C를 해결하고, 20분동안 D를 거의다 풀었을때 대회가 종료되었고 10분정도 더 디버깅 한 후에 D에서 AC를 받았습니다.

A - Coffee

coffee와 같이 문자열의 3,4번째 문자가 동일하고 5,6번째 문자가 동일하면 이 문자열은 coffee string이라고 한다고 합니다.

 

길이가 6인 문자열이 주어졌을 때 이 문자열이 coffee string인가 아닌가를 판단하는 문제였습니다.

 

B - Golden Coins

500엔짜리를 내면 1,000만큼의 행복을 얻고 5엔짜리를 내면 5 만큼의 행복을 얻는다고 합니다.

이 때, $X$원이 주어졌을 때 최대로 얻을 수 있는 행복은 얼마나 되는지 찾는 문제였습니다.

 

500엔짜리로 최대한 행복을 얻은 다음에, 남은 돈을 5엔짜리로 지불하면 되는 문제입니다.

 

$(x/500)*1000+((x\%500)/5)*5$ 를 출력하는 되는 문제였습니다.

 

C - Traveling Salesman around Lake

둘레가 $K$인 연못 주변에, 연못 북쪽(가장 위)를 중심으로 거리가 각각 $A_{i}$인 집들이 $N$개 있다고 합니다. 이 모든 집을 전부 방문하는데 걸리는 최단 거리를 구하는 문제였습니다.

 

손으로 몇 가지 경우를 그려서 해보면, 절대 한번 이동하기 시작한 방향은 바꾸면 안된다는 사실을 발견할 수 있습니다.

그림 1

그림 1을 보시면, $A+B$(빨간 실선)라는 경로로 가거나 $A+C$(파란 점선)라는 경로로 가야합니다. 그리고 원의 둘레인 $K$는 $K=A+B+C$로 표현할 수 있죠.

 

즉, 원의 둘레에서 집 사이의 거리들 중 가장 큰 값을 빼주면 우리가 모든 집을 방문할 수 있는 최소 거리를 구할 수 있다는 뜻입니다.

 

이미 집의 절대 위치는 정렬 된 상태로 주어지므로 집과 집 사이의 거리를 전부 구하는 것은 간단히 $O(N)$의 시간 복잡도로 해결할 수 있는 문제이므로, 이 문제를 쉽게 해결할 수 있습니다.

 

D - Line++

$N$개의 정점을 가지고 있고, $N$개의 간선을 가진 그래프가 있습니다.

 

이 그래프들의 모든 $i$번 정점은 $i+1$번 정점과 연결되어 있고, 방향성 그래프가 아니고 weight가 없는 그래프입니다.

이 때, $X$번 정점에서 $Y$번 정점으로 이동할 수 있는 간선을 추가한다고 할 때, 이 그래프 위의 모든 정점을 대상으로 거리가 0, 1, 2, ..., n-1인 path의 개수를 구하는 것입니다.

 

단, 1번에서 2번 정점으로 이동하는 경로와 2번에서 1번 정점으로 이동하는 경로는 동일하다고 생각합니다.

 

우선 순위 큐를 사용한 다익스트라 알고리즘의 시간 복잡도는 일반적으로 $O(ElogV)$이므로, $E=n, V=n$이므로 정점 하나에 대해 다익스트라 알고리즘을 적용하는데 $O(nlogn)$의 시간이 걸립니다.

 

정점이 모두 $n$개이고 $n\leq2000$이므로 총 $O(n^{2}logn)$의 시간복잡도로 문제를 해결할 수 있습니다.

 

E - Red and Green Apples

풀어보진 못했는데 딱 봐도 DP문제였습니다.

 

F - Distributing Integers

트리 순회 하는 문제였던 것 같은데, 읽어보지 못했습니다.

 

총평

D까지는 1시간 안에 해결할 수 있는 난이도였습니다. E와 F를 누가 빨리 푸냐에 달린 경쟁이었을 것 같습니다. 다음엔 참치 산다고 늦지 말고 정시에 참여해서 빨리 물색깔 달고 싶습니다.