이동식 저장소

오랜만? 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 부품을 계속 조립해서 완제품을 만드는데, 완제품을 만들기 위해 필요한 기본 부품의 수를 구하는 문제이다. 문제를 잘 읽고 다음의 내용을 생각할 수 있어야 한다. 못 했다고? 그럼 다음부터 하면 되지. 기본 부품이란 무엇인가? 기본 부품이란 다른 부품에 의해 제작되지 않는 부품이다. 어렵게 말하면 다른 부품에 의존성이 없는 부품이고, 쉽게 말하면 입력에서 $x$로 등장한 적이 없는 부품이다. 어떻게 계산할까? 사실 어떻게 계산할..

jh님이 주신 숙제. 22996번: 유니온 파인드 복원 준원이는 스타팅 포인트의 멤버이다. 준원이는 회사에서 병합 (merge) 연산을 수행할 때마다 포인트를 얻는다. 그래서 준원이는 C언어로 다음과 같은 코드를 작성했다. #include int par[300001]; int find( www.acmicpc.net 익숙한 Union-Find 코드가 보인다. 주어진 결과값을 이용하여 원래 입력값을 찾아야 하는 문제이다. 딱 봐도 쿼리를 만드는 방법이 매우 많고, 따라서 가장 간단한 방법을 취해야 한다. 코드포스 A~B번 스타일의 문제. 쿼리를 분석해 보자 1번 쿼리는 전형적인 merge 연산이다. 별 볼 일 없는 1번 대신 2번 쿼리에 집중해야 한다. 쿼리가 독특한데, 주어진 원소 ``v``와 같은 집합에..

16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 설명만 읽어도 감이 온다. 아.. 빡구현이구나. 엄청나게 귀찮을 것만 같은 느낌이 확 온다. 문제 자체는 크게 어렵지 않다. 다만 구현할 조건이 너무나도 많아서 문제. 5×5 판 5개가 주어질 때, 각 판을 임의로 회전한 후 판을 쌓을 수 있는 모든 순서에 대해 가능한 모든 입구-출구 쌍에 대해 출구까지 도달하기 위한 이동 횟수의 최솟값을 구해야 한다. 보통의 브루트 포스 문제는 4~5번만 구현하면 되지만, 이 문제는.... 많다. 조건을 하..

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$보다 작은 공을 구한다. 구한 공..