이동식 저장소

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 이런 구간 류의 문제는 일단 구간의 끝을 기준으로 정렬해놓고 생각해야 한다. (참고: 20440번 문제) 왜? 보내는 마을이 빠른 택배를 먼저 실으면 어떤 일이 일어날까? 다음의 입력을 생각해 보자. 5 5 2 1 10 5 4 5 10 다른 요소가 동일하다면 회전율이 높은 트럭이 더 많은 상자를 배송할 수 있다. 위의 첫 번째 택배처럼 오랫동안 트럭을 점유하고 있으면 곤란하다. 즉 택배를 싣는 마을이 아니라 택배를 내리는 마을을 기준으로 생각..

요새 글을 안 쓰는 이유는.. 쓸 게 없어서. 마이보카 2.0을 만들고 있는데 딱히 쓸 거리가 없다. 뭐 Compose 강의라도 해봐? 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 어디서 많이 본 듯한 게임의 설명이 나온다. 요약하면 어떤 공은 자신과 색깔이 다르면서 자신보다 작은 공을 사로잡을 수 있다. 각 공이 잡아먹을 수 있는 모든 공의 크기의 합을 구하고 싶다. 특정한 공 $b$가 사로잡을 수 있는 모든 공의 크기의 합을 구해 보자. $b$보다 작은 공을 구한다. 구한 공..

골3 문제로 재활 중이다. 언제까지 재활만 하냐고요? 저도 몰라요.. 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 두 가지 방법으로 풀 수 있는 문제이다. 그리디 주어지는 간선을 비용이 낮은 순서대로 정렬한다. 이때 간선에 방향이 없으므로 $(i, j)~ (i < j)$를 잇는 간선만 담는다. 빈 그래프 $graph$를 준비하고, 정렬된 각 간선에 대해 다음을 수행한다. 변수 선언: 이 간선은 정점 $i$와 $j$를 연결하며, 간선의 거리는 $cost$이다. $i$와 $j$가 연결되지 않았거나, $i$..

오랜만에 문제를 풀었다. 그동안 생각이 좀 많았어서 ㅎㅎ.. 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 너무 쉬워 그냥 매번 입력받으면서 정렬하면 그만 아닌가? 한번 입력받고 정렬하는 데 대략 $MlogM$, 입력을 총 $M$번 받으므로 테스트 케이스 하나당 시간 복잡도는 $O(M^{2}logM)$이다. 테스트 케이스의 개수까지 고려하면 풀릴 리가 없다. 그럼 어쩔까요 당연히 더 효율적인 방법을 찾아야 한다. 사실 이 문제처럼 변하는 배열에서 중앙값을 구하고 싶을 때 유용한 ..

매운 거 먹기 좋은 날씨인데.. 나는 뭐 하냐.. 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 뭔가 어려워 보이는 문제이다. 음식의 모든 조합을 먹어 보라고 했으니 $2^{N}$개의 조합을 모두 따져 볼까? $O(2^{N})$ 풀이 음식점의 모든 조합을 구하고, 모든 조합의 주헌고통지수를 더한다. 1초만에 떠올릴 수 있는 풀이지만, 당연히 맞을 리가 없다. Small 태스크만 봐도 $N=3000$이다. 아무래도 조금 더 생각해봐야 할 것 같다. $O(N^{2})$ 풀이 위에서 말했듯이, 이 음식점의 모든 음식 조합은 $2^{N}$개이다. 상식적으로 $2^{N}$개를 일일이 다 따져볼 수..