하바나바나나

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 원래는 14639번을 풀려고 했는데... 아무리 생각해도 못 풀고 힌트를 들어도 못 푸니까 cologne 님이 던져준 문제입니다. 연속된 전구가 주어지고 $i$번째 전구는 $i-1$, $i$, 그리고 $i+1$번째 전구를 toggle 할 수 있습니다. 원래의 전구 상태와 바꾸고자 하는 전구 상태가 주어질 때, 최소 toggle 횟수를 찾아야 합니다. 이는 그리디한 방법..

https://www.acmicpc.net/problem/4181 4181번: Convex Hull 때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소 www.acmicpc.net 말 그대로 컨벡스 헐을 구하는 문제입니다. 컨벡스 헐을 구할 수 있으면 그냥 구할 수 있습니다. 컨벡스 헐을 구할줄 몰라도 문제에서 어떤 점이 볼록 껍질에 포함되는지 알려주기 때문에 각도정렬을 슥삭슥삭 하면 구할 수 있습니다. 편의를 위해 반시계 방향의 시작점(x값이 가장 작은 점, 같다면 y값이 가장 작은 점)을 기준으로 기울기를 구해줍니다. 이렇게 하면 다른 모든 점들은 ..

https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 > T; for (int _ = 1; _ m; for (int i = 0; i > a >> b >> x; graph[a][b] = x; graph[b][a] = x; } for (int k = 0; k < m; k++) { for (int i = 0; i < m; i++) { for (int j = 0;..

https://www.acmicpc.net/problem/20938 20938번: 반짝반짝 이제 조금밖에 남지 않은 겨울 기분을 만끽하고 싶은 수현이는 지금부터라도 크리스마스 트리를 장식하려고 한다. 크리스마스 트리는 전구 스트립으로 두른다. 전구 스트립에는 전구 $N$개가 일 www.acmicpc.net dp를 두 번 돌리면 풀리는 문제입니다. $\mathcal{O}(N^2)$에 임의의 $l$과 $r$에 대해서 $l$부터 $r$까지의 조각의 기댓값을 구할 수 있습니다. 이 때 나이브하게 짜면 $\mathcal{O}(N^3)$의 시간이 걸리므로 메모이제이션을 통해 최적화를 해줘야 합니다. 이후 주어진 전구를 어떻게 $k$개 이하의 조각으로 나눠야 최적인지 찾으면 됩니다. 이는 $\mathcal{O}(KN..

https://www.acmicpc.net/problem/17308 17308번: Getting-Up Syndrome In the 21st century, many people have contracted an odd disorder – getting-up syndrome. Symptoms include having great difficulty getting out of bed in the morning and feeling out of sorts even after getting up. As a generally high-spirited teenager, ATM www.acmicpc.net 지문이 영어인데다 길지만 정리하자면 0부터 $m$ 사이의 주어진 쿼리의 연산들을 모두 적용했을 때, 나올 수 있..

https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 매 쿼리마다 $S$가 주어졌을 때 $S$ 안의 정점들 주 연결되어 있는 정점 쌍의 개수를 찾는 문제입니다. 문제를 정리하면, $S$가 주어질 때 $S$안의 정점들이 몇 개의 컴포넌트로 나누어지는지, 그리고 각 컴포넌트에는 몇 개의 정점이 있는지 찾는 문제라고도 할 수 있습니다. 컴포넌트 내의 정점들은 모두 서로 연결되어 있다고 할 수 있으므로 매 컴포넌트마다 컴포넌트 안의 정점에서 두 개..

https://www.acmicpc.net/problem/23090 23090번: 난민 문제의 답을 공백으로 구분하여 \(N\)줄에 걸쳐 출력한다. \(i\)번째 줄에, \(1\)번째 부터 \(i\)번째까지 이주해온 난민들이 정수시설까지 이동하는 거리의 합이 최소가 되도록 하는 정수시설의 \(y\ www.acmicpc.net 블로그에 올렸던 쌀 창고 + 중앙값 구하기인 문제입니다. https://havana723.tistory.com/16 BOJ 5821 쌀 창고 https://www.acmicpc.net/problem/5821 5821번: 쌀 창고 쌀 창고 이 경우에는 창고의 위치에 대한 여러 개의 최적 위치가 있다: 10 이상 14 이하의 어느 정수 위치에든지 쌀 창고를 둘 수 있다. 위의 그림은 최..

https://www.acmicpc.net/problem/24456 24456번: 초콜릿 훔쳐 먹기 첫 번째 줄에는 세 정수 $N,\ M,\ K$가 공백으로 구분되어 입력된다. ($1 \le N,\ M \le 10\,000$, $0 \le K \le N \times M$) www.acmicpc.net 1부터 $NM$까지의 모든 수에 대해 해당 수를 두 수의 곱으로 표현하는 모든 경우를 구하는 문제라고도 생각할 수 있습니다. 단순히 모든 약수를 확인한다면 $\mathcal{O}({(NM)}^2)$의 시간이 걸릴 것이라고 생각했고 커팅하는데 시간이 걸렸습니다. 커팅은 소인수분해를 하듯이 하면 됩니다. $x$의 약수를 확인할 때 $\sqrt{x}$까지의 수로 나누어지는지만 확인하면 두 수의 곱으로 표현하는 모..

https://www.acmicpc.net/problem/24914 24914번: Split the SSHS 첫째 줄에 세 정수 N, M, 그리고 Q가 공백으로 구분되어 주어진다. 둘째 줄부터 N째 줄까지 N - 1 개의 줄에 세 정수 ui, vi, wi가 공백으로 구분되어 주어지며, 색 wi로 칠해진 i 번 길이 ui 번 건물과 vi www.acmicpc.net 어떻게 맨 처음에 조각의 수를 셀 수 있을까 고민하다가 조각의 개수가 (각 정점에 연결되어 있는 색의 종류 - 1)을 모두 더한 다음 1을 더해준 값이라는 것을 발견했습니다. 트리 몇 개 그려보고 맞는 거 같아서 짜서 맞았습니다. 증명은 다음과 같습니다. 이 문제는 트리 하나가 $k$개의 트리(조각)으로 나누어질 때, $k$를 구하는 문제가 됩..

https://www.acmicpc.net/problem/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점 www.acmicpc.net 처음에 그리디로 한 네 번쯤 삽질하다가 다 예제에 막히고 포기했습니다. 태그 까고 나서 DP인걸 알고도 하루 종일 고민했는데 안 풀려서 cologne 님께 풀이를 들었습니다. $dp[l][r]$을 $l$부터 $r$까지의 구간에서 매칭했을 때의 최솟값으로 두면 됩니다. 역추적도 필요한데, 메모이제이션을 할 때 $l$이 어느 점과 이어졌는지를 기록하면 역추적을 할 수 있..