STUDY

도서관 문제 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M 권의 책을 들 수 있다. 입력 첫째 줄에 책의 개수 N 과, 세준이가 한 번에 들 수 있는 책의 개수 M 이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N 과 M 은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 ..

k개의 부분 배열 문제 $N$개의 서로 다른 정수를 가진 배열 $A$가 주어진다. 당신은 어제 공격력이 양의 정수 $k$인 칼을 받았다. 이 칼이 있으면 배열에 아래와 같은 연산을 적용할 수 있다. 배열을 $k$개의 조각으로 자른다. $k$개의 조각을 원하는 순서대로 재배열한다. 재배열한 순서대로 조각들을 다시 합친다. 당신은 배열 $A$에 이 연산을 원하는 횟수만큼 적용하여 (한 번도 적용하지 않아도 괜찮다) 오름차순으로 정렬하려고 한다. $k$의 값에 따라 이 연산을 적절히 적용하면 $A$를 정렬하는 것이 가능할 수도 있고, 연산을 어떻게 잘 적용해도 정렬할 수 있는 방법이 없을 수도 있다. 이 때, 배열 $A$를 정렬할 수 있는 가장 작은 양의 정수 $k$의 값을 구하는 프로그램을 작성하자. 입력 ..

선 긋기 문제 매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자. 이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다. 입력 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. 출력 첫째 줄에 그은 선의 총 길이를 출력한다. 선을 긋기 때문에 포함하는..

휴먼 파이프라인 문제 오늘은 중요한 날이다. SUAPC가 있는 날이기 때문이다. 이렇게 중요한 날이지만 안타깝게도 일을 해야 한다. 오늘 해야 할 일은 상자 K$K$개를 적절한 곳으로 옮겨야 하는 일이다. 상자 K$K$개는 너무 많아서 아무래도 혼자서 전부 나를 수는 없기 때문에, N$N$명의 SUAPC 참가자들이 상자를 나르기 위해 모여 있다. N$N$명 모두가 일을 최대한 빠르게 마치고 SUAPC에 참가하고 싶어한다. 참가자들은 두 팀으로 나눠져서 작업을 진행하기로 했다. 두 팀이 같은 수의 상자를 옮길 필요는 없다. 두 팀 모두 적어도 한 명은 포함되어야 한다. 각 사람의 분당 작업 속도는 vi$v_i$며 팀의 작업 속도는 ($($해당 팀에 속한 사람들의 작업 속도 중 가장 느린 작업 속도)×($)..

ATM 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하..

모노톤길 문제 제주 올레길 코스로 유명한 산책로가 있다. 산책로의 입구는 산책로에서 가장 서쪽에 위치하고 있다. 이 산책로는 단순 경로이며 수평 구간과 수직 구간으로만 구성되어 있어 모든 코너에서 90도 각도로 왼쪽 또는 오른쪽으로 회전만 할 수 있다. 또한 입구에서 출구 방향으로 걸어갈 때 동쪽에서 서쪽으로 이동을 전혀 하지 않아도, 즉, 보행자의 현재 위치를 나타내는 좌표의 x축 값이 작아지는 경우가 없이도 출구까지 도달할 수 있다. 그래서 이 산책로를 모노톤길이라고 부른다. 그림 1은 모노톤길의 예를 보여준다. 그림 1. 모노톤길의 예 이 산책로에는 n개의 카페가 곳곳에 들어서 있다. 특히 입구와 출구, 그리고 모든 코너에는 카페가 들어서 있다. 올레길 코스 관리자인 김씨는 이 산책로에 들어서 있는..

정육점 문제 은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다. 각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다. 각 덩..

대통령 선거 문제 대선이 끝난 후 2주가 지났으나 여전히 결과는 발표되지 않았다. 결과가 궁금한 성제는 결과를 직접 미리 알아보기로 했다. 성제는 모종의 방법으로 투표에 참여한 모든 사람들에 대해 한 명도 빠짐없이 선호도 조사를 마쳤다. 성제는 투표에 참여한 사람들이 항상 선호도에 따라 투표했음을 알고 있다. 예를 들어 대통령 후보가 5명이고 어떤 유권자의 선호도가 [3, 2, 5, 1, 4] 인 상태에서 2번 후보와 4번 후보가 경합을 벌인다면, 이 유권자는 2번 후보에게 투표한다. 투표의 전체 규칙은 아래와 같다. C명의 후보와 V명의 유권자가 있다. 각 후보는 1에서 C까지의 정수로 표현되며, V는 항상 홀수이다. 투표는 2회에 걸쳐 진행된다. 첫 투표에서는 모든 후보가 표를 받을 수 있으며, 만일..

회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231..