티스토리 뷰

AtCoder Beginner Contest 160

 

AtCoder Beginner Contest 160 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

오랜만에 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를 누가 빨리 푸냐에 달린 경쟁이었을 것 같습니다. 다음엔 참치 산다고 늦지 말고 정시에 참여해서 빨리 물색깔 달고 싶습니다.

 

 

'알고리즘 > AtCoder' 카테고리의 다른 글

AtCoder Beginner Contest 169 회고  (0) 2020.06.04
AtCoder Beginner Contest 136 회고  (0) 2019.08.05
AtCoder Beginner Contest #114  (0) 2018.12.02
댓글
댓글쓰기 폼
공지사항
Total
23,335
Today
0
Yesterday
10
링크
TAG
more
«   2022/11   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함