이동식 저장소

단계별로 풀어보기 따라가는 중. 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net $N$명의 사람과 $N$개의 일이 있다. $i$번 사람이 $j$번 일을 할 때의 비용 $D[i][j]$가 주어질 때, 비용을 최소로 하면서 각 사람에게 하나의 일을 할당해 보자. 딱 봐도 dp이고, 선택된 일의 집합을 표현해야 하므로 비트마스크 dp를 적용할 수 있다. 마침 $N$이 20으로 매우 작기도 하고. 현재 남아있는 일의 집합을 $j$(비트마스크)일 때 $i$번 사람에게 일을 할당하여 얻을 수 있는 비용의 ..

10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2042번 구간 합 구하기 1에서는 수가 하나씩 바뀌므로 세그먼트 트리 또는 펜윅 트리를 이용하여 문제를 풀 수 있다.. 그런데 이 문제에서는 $[l,~r]$ 구간의 값이 바뀐다. 따라서 일반적인 세그먼트 or 펜윅 트리를 이용해 값을 갱신하면 한 번의 갱신에 최대 $O(NlogN)$의 시간이 걸리고, 시간 초과를 받을 수밖에 없다. 일반적으로 쿼리 문제에서는 쿼리를 로그 시간 안에 해결해야 한다...

11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 원래 건물을 잇는 모든 길은 양방향이었는데, 공사 때문에 몇몇 길이 일방통행으로 바뀌어 버렸다. 이제 두 건물 사이를 오가려면 일방통행 길을 최소한 몇 개나 양방향으로 바꿔야 하는지 알아보자. 흠.. 그런데 쿼리가 최대 3만 개 주어진다. 매번 길을 탐색하면 시간 초과가 날 것 같다. 따라서 모든 $s,~e$ 쌍에 대해 정답을 미리 구해 놓아야 한다. 풀이 다익스트라 또는 플로이드 와샬 알고리즘으로 풀 수 있다. 두 방법 모두 주어지는 단방향 간선 $u,~v$에..

2248번: 이진수 찾기 N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수 www.acmicpc.net $N$자리의 이진수 중에서 1인 비트가 $L$개 이하인 이진수를 오름차순으로 정렬했을 때, $I$번쨰 이진수를 구하는 문제이다. 이진수는 0으로 시작할 수 있음에 주의하자. 이진수를 결정하려면 이진수의 각 자리가 0인지 1인지 결정해야 한다. 현재 자리가 0과 1 중 무엇인지 결정하려면, 현재 자리를 0(또는 1)로 결정했을 때 몇 개의 이진수를 만들 수 있는지 알아야 한다. 문제를 쉽게 만들기 위해, $N$자리의 이진수를 만드는 데 1을 정확..

세포야 일해라! 17401번: 일하는 세포 출력은 N개의 줄로 구성되며, i 번째 줄에는 N개의 정수 xi1, xi2, ..., xiN를 공백으로 구분하여 출력해야 한다. xij는 0초 때 거점 i 에서 출발하여 정확히 D초 때 거점 j에 위치하게 되는 경로의 수를 1 www.acmicpc.net 적혈구는 우리 몸 속의 거점을 돌아다니면서 산소를 운반한다. 적혈구가 혈관을 타고 한 거점에서 다른 거점으로 이동하는 데에는 1초가 걸린다. 그런데 매 초마다 우리 몸 속의 혈관 배치가 달라진다. 다행히 백혈구가 관찰한 결과 $T$초마다 같은 배치가 반복된다는 사실을 알게 되었다. 적혈구가 $D$초 동안 이동할 때, 임의의 한 거점에서 다른 거점으로 이동할 수 있는 경로의 수를 구하자. 구하는 답이 매우 커질 ..