이동식 저장소

1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다 www.acmicpc.net 최소의 비용으로 적어도 p개의 발전소를 켜야 하는 문제이다. 문제를 풀기 전에 짚고 넘어가야 할 점이 있다. 1. 발전소를 동시에 켜는 것이 아니며, 이전에 켠 발전소로 다른 발전소를 켤 수 있다. 2. ..

BOJ에서 푸는 문제 중에는 알고리즘 대회에서 출제되었던 문제가 있습니다. 대부분의 대회에서는 대회 당시에 사용했던 입력 데이터를 제공하고 있습니다. 이미 데이터를 활용하고 계신 분들도 많으리라 생각합니다. 그런데 가끔 제공되는 데이터를 활용하기 불편한 경우가 있습니다. 예를 들어 1개의 파일에 매우 많은 테스트 케이스가 있는 경우, 출력이 너무 길어서 출력을 검증할 수가 없습니다. 출력이 올바른지, 올바르지 않다면 어디서 틀렸는지를 수작업으로 찾기가 매우 힘들기 때문입니다. 예전에 저 역시 이런 문제 때문에 데이터를 충분히 활용하지 못했습니다. 그러다가 얼마 전에는 아주 좋은 조합을 발견했습니다. 바로 Visual Studio Code + Windows Subsystem for Linux입니다. 지금부..

2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 www.acmicpc.net 추를 적절히 이용해서 주어진 무게를 잴 수 있을까? 브루트 포스를 이용하여 가장 쉽게 문제를 해결할 수 있다. 그러나 이 문제에서는 추가 최대 30개이므로 2^30개의 가능성을 모두 탐색하다간 시간 초과를..

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. www.acmicpc.net 벽 부수고 이동하기라는 제목이 달려 있지만, 원본과는 전혀 다른 문제이다. 각 벽에 대해 다음을 수행한다. 1. 벽을 부순다. 2. 부순 위치로부터 이동할 수 있는 칸의 개수를 센다. 이때 출발점도 세어야 한다. 아주 나이브한 방법으로, 모든 벽마다 BFS를 수행하면..

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다. www.acmicpc.net 여러 개의 부분 순서가 주어진다. 우리의 목표는 모든 부분 순서를 만족시키는 전체 순서를 작성하는 것이다. 순서를 정해야 한다는 말에서 알 수 있듯이, 위상 정렬을 적용하면 된다. 위상 정렬을 수행하기 위해서는 그래프를 만들어야 한다. 우리는 주어진 입력으로부터 그래프를 쉽게 만들 수 있다. 예를 들어 예제 ..