이틀 전에 이어서 다섯 문제를 풀었다. 시작 난이도는 P4
https://www.acmicpc.net/problem/17131
17131번 여우가 정보섬에 올라온 이유 P4
예전에 단계별로 풀어보기에서 이름을 봤던 문제라(풀어보지는 않았다) 태그를 보려하지 않았음에도 의도치 않게 세그트리 + 스위핑 문제라는 것을 알고 있었다. y값에 따라 내림차순을 정렬한 뒤 구간합 세그먼트 트리를 사용해 x좌표의 왼쪽에 있는 별의 수와 오른쪽에 있는 별의 수를 곱해서 정답에 더하고 x좌표를 업데이트 해주면 되는 문제다.
https://www.acmicpc.net/problem/2126
2126번 지진 P3
문제를 보고 처음에는 MST를 떠올렸으나 그때그때 간선의 이득이 변하기 때문에 사용할 수 없다고 생각하고 N이 작다보니 굉장히 여러 알고리즘을 생각하다가 결국 풀지 못했는데 식을 변형 한뒤 매개변수 탐색 + MST로 푸는 문제였다… 실수형 변수로 매개변수 탐색을하는 문제를 풀어본 적이 없어서 그게 가능하리라 생각하지 못했다.
https://www.acmicpc.net/problem/1048
1048번 유니콘 P4
각각의 칸에 i번째 차례로 방문했을때 최종적인 결과를 dp배열에 저장해놓는 방식으로 문제를 풀었는데 tle가 나왔고 잘 생각해보니 최악의 경우 시간 복잡도가 O(N^4)정도가 나올거 같았다(N<=300). kmp부터 시작해서 별에별 방법으로 최적화를 해보려다가 결국 풀지 못했는데 dp인 건 맞았지만 방향성이 완전히 다른 구간합 + dp 문제였다.
https://www.acmicpc.net/problem/23760
23760번 까다로운 아이들과 선물 상자 P5
보자마자 세그먼트 트리 문제라는게 보였고 너무 반가웠다. 문제 편식 안 하려고 시작한 랜덤 디펜스인데 익숙한 알고리즘이 나오면 반가운 건 어쩔 수 없나보다. 구간합 세그먼트 트리로 i번째로 큰 수를 찾는 문제이다.
https://www.acmicpc.net/problem/28433
28433번 게리맨더링
특별한 알고리즘의 사용이 없는 그리디 문제, 푸는 것에 성공했고 자세한 풀이는 따로 글을 작성했다.
https://yongjun49.github.io/baekjoon/BOJ(백준)-28433번-게리맨더링/
여담이지만 게리맨더링이 무슨 뜻인가 하고 검색을 해봤는데 문제 네이밍을 센스있게 잘한 거 같다.
틀린 문제가 꽤 있었지만 그래도 다시 문제 난이도가 P3까지 올라가서 기분 좋게 마무리할 수 있었다.
댓글남기기