이동식 저장소

16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 정수 $x$에 다음 두 연산 중 하나를 $N-1$번 적용하여 길이가 $N$인 수열 $A$를 만든다. $x$를 $3$으로 나눈다. 이때 $x$는 3으로 나누어떨어져야 한다. $x$에 $2$를 곱한다. $A$의 수를 무작위로 섞은 수열 $B$가 주어졌을 때, $A$를 구하는 문제이다. $A$에 속하는 정수 $y$에 대해, $y$ 앞에는 $3y$ 또는 $y/2$가 올 수 있고, $y$ 뒤에는 $y/3$ 또는 $2y$가 올 수 있다. 우리는 이 수열의 ..

오랜만이다 그죠? 13325번: 이진 트리 입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가 www.acmicpc.net 문제의 조건은 다음과 같다. 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같게 하면서 에지 가중치들의 총합이 최소가 되도록 하자. 어떻게 증가시킬 것인가 2번 조건을 보면, 루트에서 모든 리프까지의 거리가 같아야 한다. 동시에 3번 조건에 의해 루트에서 각 리프까지의 거리는 최대한 작은 값이어야 한다. 이 값을 ``target``이라고 정의하자. ``target``을 어떻게 구해야 할까? 조건을 종합하면 ``target..

오랜만? 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번만 구현하면 되지만, 이 문제는.... 많다. 조건을 하..