하바나바나나

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$이 어느 점과 이어졌는지를 기록하면 역추적을 할 수 있..

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 교육적인 슬라이딩 윈도우 문제입니다. 원형으로 돌면서 $k$짜리 길이의 초밥들을 관리해주면 됩니다. 초밥이 추가될 때마다 visited 값을 늘려주고 초밥이 제거될 때마다 visited 값을 줄여주면 쉽게 구현할 수 있습니다. 쿠폰의 경우, 현재 가지고 있는 초밥 중 $c$번 초밥이 있는지 확인해주면 됩니다. 아래는 코드입니다. #include #def..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹을 사용해 풀 수 있는 문제입니다. n-queen 문제와 비슷하게 비숍을 하나씩 놓는다고 생각하고, 하나의 비숍이 놓일 때 그 대각선에 있는 칸들은 전부 갈 수 없다고 표시해주면 됩니다. 다만 나이브하게 백트래킹을 돌리면 시간초과를 받게 되고, 체스칸의 흰색 영역과 검정색 영역을 나눠서 (비숍은 한 색으로만 이동할 수 있으므로) 풀면 풀 수 있습니다. 이 아이디어를 생각하는 것이 어려웠습니다. 아래..