jay153의 PS 일지

문제 링크 코드http://boj.kr/942a617eb273499fa12250bd1e91dfb5 2023 충남대학교 SW-IT Contest Division 1 K 난이도 : P3 Elapse Time : 70min 어떤 위치가 며칠 후에 꽃이 필지 구해보면 그 위치에서 초기에 꽃을 심은 있는 위치들과의 거리 중 최솟값이 된다. 모든 위치에서의 값 중 최댓값을 구하는 것이 이 문제의 요구사항이다. 이 문제에서 가장 눈이 간 것은 $M$에 비해 $N$의 범위가 작다는 것이다. 처음에는 모든 위치 중 어떻게 위치의 후보를 줄일지 생각했다. 하지만 $K$개의 점들의 위치 관계가 항상 달라지는데 이를 일반화하기는 쉽지 않아 보였다. 두 번째로 한 생각은 파라메트릭 서치가 사용 가능한지이다. 그러나 방법이 쉽게..

https://www.acmicpc.net/problem/17050  코드http://boj.kr/70deeac7b2b2446487665d909f26a5a0 Croatian Open Competition in Informatics 2018/2019 Contest #5 난이도 : P4 Elapse Time : 25min 문제를 읽고 트라이를 쓰면 편할 것 같다는 느낌이 들었다. '?'가 처리 가능한지와 '?'를 처리할 때 시간 복잡도가 커지지 않는지가 관건이었다. 트라이에 '?'가 포함된 단어를 삽입할 때와 트라이에서 '?'가 포함된 단어와 일치할 수 있는 단어의 개수를 세어 답에 더해줄 때 2가지를 처리해야 했다. '?'가 포함된 단어를 삽입하는 것은 트라이를 만들 때 인덱스 하나를 추가해 주면 되기 때..

https://www.acmicpc.net/problem/14849 코드http://boj.kr/bbf8635a8ab74ad7bfe625ff7021af42 난이도 : P2 Elapse Time : 90min 이 문제를 보고 $T=100$, $q=100$, $v=10^5$인 것이 먼저 눈이 들어왔다. $O(Tqv)$의 코드는 시간에 안 들어올 것이기 때문에 $c_1$, $c_2$, $c_3$, $c_4$를 입력받고 쿼리를 입력받기 전에 무언가를 미리 계산을 해놔야겠다는 생각을 했다. 동전을 무제한으로 사용 가능할 때 $x$를 만드는 경우의 수를 구해놓으면 쿼리 처리를 할 수 있을지 생각해 보았다. 쿼리에서는 동전 개수에 제한이 있는데 포함과 배제로 제한보다 많이 사용하는 경우를 빼주는 것은 동전 종류가 4..

https://www.acmicpc.net/problem/1349 코드http://boj.kr/01722eeb80874eb5a548de9a33448799 난이도 : P2 Elapse Time : 50min 문제를 보고 든 생각은 2개였다. 최종적으로 모든 도시 쌍이 연결되어 있어야 하고 그 비용을 최소화하는 문제이기 때문에 최소 스패닝 트리와 연관이 있을 것 같다는 것과 $N$이 많이 작아 모든 도시 쌍을 다 살펴보는 것이 가능하다는 것이었다. 이 문제에서는 도로의 추가가 없더라도 들어갈 수밖에 없는 고정 비용이 존재한다. 각 도시별로 추가적인 집을 짓는 데 $ \frac{(A_i-B_i)(A_i+B_i-1)C_i}{2}$의 비용이 들고, 연결된 $(i,j)$의 쌍에 대해 $(A_i-B_i)(A_j-B_..