량베개

17942번 알고리즘 공부 G1 문제늘 돈이 부족한 희정이는 HCPC에 참가하여 좋은 성적을 거두어서 상금을 타기로 마음먹었다. 이를 위해 먼저 출제위원장인 정호의 노트북을 해킹하여 N개의 알고리즘을 출제 범위로 두고 문제가 출제된다는 사실을 알게 되었다. 출제 범위를 알았으니 이제 희정이에게 남은 것은 알고리즘을 공부하는 것이다. 알고리즘 공부에는 사실 특별한 규칙이 숨어있는데 이는 다음과 같다. 각 알고리즘들을 처음 배울 때에는 Ki만큼의 알고리즘 공부량이 필요하다. 그리고 몇몇 알고리즘은 서로 연관성이 있어 어느 한 알고리즘을 배우면 다른 특정한 알고리즘을 배울 때 필요한 공부량이 줄어드는 경우가 있다. 한 알고리즘을 배울 때 필요한 공부량이 여러 개의 다른 알고리즘에 의해서 줄어드는 경우는 그 감..

15321번 이상한 토너먼트 G2 문제천하제일코딩대회가 열리게 되었다. 천하제일코딩대회는 1대 1 대결 토너먼트 방식으로 진행이 된다. 대회 운영을 맡은 전설의 코더 천민호는 개인의 코딩실력을 정확히 측정하는 스카우터를 만들어 각 참가자의 코딩력(능력치)을 알고 있다. 코딩력이 다른 두 사람이 대결을 하게되면 무조건 코딩력이 높은 사람이 승리하게 된다. (사실상 우승자는 정해져있는 것이나 다름없다.) 토너먼트 대진표를 작성하기 귀찮았던 민호는 우선 참가신청한 사람들의 순서대로 일렬로 나열한 후, 선을 그어 대진표를 완성하려 한다. 민호는 대회의 재미를 위해서 관중들이 지루하지 않도록 대진표를 완성하고 싶다. 일반적으로 관중들의 지루함 정도는 두 대결자의 코딩력의 차에 비례한다. 관중들의 지루함 = 두 대..

32143번 카드 게임(Hard ) G3 문제당신은 카드 게임을 하고 있다. 상대의 체력은 H이며, 당신은 다양한 공격력을 가진 카드를 총 N개 가지고 있다. 만약 어떤 카드를 사용하여 공격하면, 상대의 체력은 그 카드의 공격력만큼 줄어든다. 체력이 0 이하가 되면 죽는다. 당신은 패에 있는 카드를 아끼기 위해서 카드를 최대한 적게 써서 상대를 죽이려고 한다. 이때, 다양한 상황에 대비하기 위해서, Q개의 카드에 대하여 각 카드가 순서대로 추가되는 상황에 대해 이 문제를 풀려고 한다. 각 카드가 추가되었을 때 상대를 죽이기 위해 사용해야 하는 카드 개수의 최솟값을 구하거나, 죽이는 것이 불가능한지 판별하여라. 여기서 각 쿼리는 누적되며, 각 카드는 쿼리당 1번만 사용할 수 있다.입력첫 번째 줄에 H가 주..

1948번 임계경로 P5 문제월드 나라는 모든 도로가 일방통행인 도로이고, 사이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트하여라. 출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로..

1939번 중량제한 G3 문제N(2 ≤ N ≤ 10,000) 개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다. 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 ..

2152번 여행 계획 세우기 P2  문제평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1 ≤ N ≤ 10,000) 개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을 거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다. 태희는 다시 비행로에 대해 조사를 하였고, 총 M(1 ≤ M ≤ 100,000) 개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1 ≤ S ≤ N) 번 도시에서 시작해서 T(1 ≤ T ≤ N) 번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다.도..

17297번 Messi Gimossi G4 문제메시는 축구 선수이다. 메시는 기분이 좋다.messi(1): Messimessi(2)​​: Messi Gimossimessi(3)​​​​​​: Messi Gimossi Messimessi(4): Messi Gimossi Messi Messi Gimossimessi(5): Messi Gimossi Messi Messi Gimossi Messi Gimossi Messi메시의 외침은 피보나치수열과 유사하게 정의된다.messi(N)은 messi(N-1), 공백, messi(N-2)을 차례로 이어붙여서 만든 문자열이다. 욱제는 N이 충분히 클 때, messi(N)의 M번째 글자가 뭔지 궁금해졌다.입력정수 M이 주어진다. (1 ≤ M ≤ 2^30-1)출력N이 충분히 클..

1516번 게임 개발 G3  문제숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다. 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 ..

최장 증가 부분 수열(LIS)에 해당하는 문제 시리즈이다.입력과 출력, 시간 복잡도와 수의 범위에 따라 S2에서 P5까지 난이도가 준비되어 있다. 문제를 풀 당시에는 1 -> 4 -> 2 -> 3 -> 5 순으로 풀이했다.LIS를 처음 접한다면 위 순서대로 푸는 것이 좋을 것이라 생각한다. 11053번 가장 긴 증가하는 부분 수열 / S2수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다. 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있..