어제에 이어서 다섯 문제를 풀었다. 시작 난이도는 P5
https://www.acmicpc.net/problem/10165
10165번 버스 노선 P5
문제를 보자마자 스위핑과 관련된 문제라는 느낌을 강하게 받았지만 풀이를 떠올리지 못했다. 예상대로 스위핑과 관련된 문제였지만 나에게 익숙한 imos가 아닌 line 스위핑에 가까운 문제였다.
https://www.acmicpc.net/problem/1060
1060번 좋은 수 G1
L과 N의 범위가 아주 적기 때문에 집합에 있는 수들 사이의 구간 각각에서의 최적값을 빠르게 뽑아낼 수 있으면 매번 모든 구간을 순회하면서 비교하여 문제를 해결하는 것이 가능하다. 다만 구현 중에 놓치기 쉬운 부분이 꽤 많아 보였다.
https://www.acmicpc.net/problem/1321
1321번 군인 P5
1168번 요세푸스 문제2의 선형 버전, 각 팀을 노드로 구간합 세그먼트 트리를 구현하여 1번 쿼리를 해결 가능하고 2번 쿼리는 내가 찾으려는 군인이 i번 군인일 때 왼쪽 노드의 값이 i이상이면 왼쪽 노드로 가서 쿼리를 진행하고 그렇지 않으면 오른쪽 노드로 가되 i번이 아니라 i에서 왼쪽 노드의 값을 뺀 번호를 오른쪽 노드에서 찾게하는 식으로 구현하면 된다.
https://www.acmicpc.net/problem/22959
22959번 신촌 수열과 쿼리 P4
바로 전 문제인 1321번과 약간 비슷한 듯 하면서도 더 어려운 문제. 세그먼트 트리로 구현할까 하다가 어떻게 구현할지 이미지가 조금 불확실해서 최근에 한 번 배우고 쓴 적이 없던 제곱근 분할법을 이용해 좀 더 직관적으로 구현을 해봤는데 AC를 받았다.
https://www.acmicpc.net/problem/14959
14959번 Slot Machines P3
최단 길이의 주기를 수열의 뒤에서부터 구해주면 문제가 해결 될 것이라는 것은 파악했지만 어떻게 주기를 구할지가 생각이 나지 않아 풀지 못했는데 찾아보니 KMP의 실패함수로 해결이 가능했고 사실 유사한 문제를 예전에 풀어본 적이 있었다…
익숙한 구간 쿼리 문제가 꽤 많이 나와서 상당히 티어가 높게 올라갔는데 마지막 kmp 문제를 틀린게 상당히 아쉬웠다.
댓글남기기