문제 링크https://www.acmicpc.net/problem/14590 문제고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승부가 나서 N명의 선수들의 순위표가 만들어졌다.  순위표를 본 현수는 절규하였다. ‘내가 공동 꼴지라고? 꼴지라니... 아니, 내가 꼴지라니! 이게 무슨 소리야! 아핡핡핡’ 이윽고 현수는 자기합리화를 하기 시작했다. ‘내가 한용이를 이겼고, 한용이는 세찬이를 이겼고, 세찬이는 찬우를 이겼고, 찬우는 태양이를 이겼고... 그러니 내가 나머지 전부를 이겼네!’현수와 마찬가지로 공동 꼴지인 태양이는 현수와 함께 자기합리화를 해보려고 하..

문제 링크https://www.acmicpc.net/problem/1348 문제세준 주차장은 R×C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.보통 모든 차는 현재 위치에서 가장 가까운 위치에 있는 주차 구역에 주차를 하려고 한다. 하지만, 다음과 같이 생긴 주차장이라면 현재 위치에서 가장 가까운 위치에 주차하는 것이 비효율적이다..C.....P.X...XX.......X..PXX.....C..... ‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.만약 아래에 있는 차가 현재..

문제 링크https://www.acmicpc.net/problem/24519  문제외판원 순회 문제는 영어로 Traveling Salesman Problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 이 중 변종 문제 중 하나인 Bottleneck Traveling Salesman Problem (BTSP) 문제를 살펴보자.정점의 개수가 N개, 비용이 있는 간선이 M개인 방향 그래프가 주어진다. 어느 한 정점에서 출발해, 출발한 정점을 제외한 N − 1개의 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회를 찾으려고 한다. 이러한 순회는 여러 가지가 있을 수 있는데, 정점 간 이동 비용의 최댓값을 최소화하려고 한다.그래프..

문제 링크https://www.acmicpc.net/problem/30975  문제진주 나들이를 온 보선이는 경상국립대 정문 쪽 연못 산책길을 걷다가 울고 있는 동기 원우를 발견했다. 반가움보다 안쓰러움이 앞선 보선이는 원우한테 다가가서 울고 있는 이유를 물어봤다. 원우는 울면서 "교수님께서 경상국립대에서 출발해 경상국립대 주변에 있는 모든 동네에 가서 하늘 사진을 찍은 다음, 다시 경상국립대로 돌아오라는 심부름을 시키셨는데 거절을 못했어. 그런데 어떻게 심부름을 끝내야 할지 모르겠어."라고 대답했다. 약간 모자라지만 착한 원우를 위해 보선이가 대신 심부름을 맡기로 했다.경상국립대 주변에 있는 동네는 총 N개이며, 각 동네는 1번부터 차례대로 번호가 부여되어 있다. 또한, 보선이는 편의상 경상국립대가 N..

문제 링크https://www.acmicpc.net/problem/30976 문제진주 나들이를 온 보선이는 목이 너무 말라서 경상국립대 앞에 있는 한 카페에 들어갔다. 그 카페에서는 진주교육대 여학생 N명과 연암공과대 남학생 M명이 모여서 미팅을 하고 있었다.이 미팅에는 신기한 사실이 하나 있는데, 바로 미팅 중인 학생들의 상대에 대한 선호 여부는 키라는 요소 한 가지에만 영향을 받는다는 것이다. 구체적으로, 여학생들은 자신의 선호 기준보다 키가 작은 남학생만을 선호한다. 그리고 남학생들은 자신의 선호 기준보다 키가 큰 여학생만을 선호한다.마침 이 카페에는 자칭 사랑의 큐피드 재혁이도 있었다. 이 미팅에 관심이 생긴 재혁이는 미팅 중인 테이블에서 오가는 얘기를 열심히 엿들어 미팅 중인 모든 학생들의 선호..

문제 링크https://www.acmicpc.net/problem/1219 문제오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.오민식은 고민에 빠졌다.어떻게 하면 최대 이윤을 낼 수 있을까?이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다.오민식은 도착 도..

문제 링크https://www.acmicpc.net/problem/7578 문제어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다또한, 각 기계에는 식별번호가 붙어있으며, 짝이 맺어진 기계끼리는 같은 식별번호가 붙어있다. 즉, 각 열에 있는 N개의 기계끼리는 서로 다른 식별번호를 가지고 있으며, 반대쪽 열에 있는 같은 식별번호를 가진 기계와 케이블로 이어져 있다.공장 작업의 효율성을 위해 기계들은 짝..

문제 링크https://www.acmicpc.net/problem/2532 문제1부터 N까지 번호가 붙여져 있는 N마리 서로 다른 동물이 있다. 모든 동물은 동일한 하나의 수평선 상에서 연속된 구간 내에서 활동한다. 이 구간을 그 동물의 활동영역이라 한다. 동물의 활동영역은 구간의 왼쪽 위치와 오른쪽 위치 쌍으로 나타낸다. 예를 들어, 7마리 동물의 활동영역이 다음 그림과 같다고 하자. 각 동물의 활동 영역은 선분으로 나타내어져 있다. 아래에서 동물 1의 활동영역은 (2, 4), 동물 2의 활동영역은 (6, 10), ..., 동물 7의 활동영역은 (3, 4)이다. 활동영역이 (x1, x2)인 동물 i와 (x3, x4)인 동물 j에 대하여, 다음 세 조건 중 하나를 만족하면 i가 j보다 먹이사슬에서 상위에..

문제 링크https://www.acmicpc.net/problem/2995 문제상근이는 생일 선물로 구간 N개를 받았다. 여기서 말하는 구간이란 수의 구간이며, [A, B]와 같은 구간이다. 구간을 어떻게 선물로 받았는 지는 잘 모르겠지만, 진짜로 그 수학에 나오는 구간이다.상근이는 자신이 가지고 있는 구간 중에서 아래와 같은 조건을 만족하는 가장 긴 서로 다른 구간의 수열을 찾으려고 한다.수열에 포함되는 모든 구간은 다음 위치에 있는 구간을 포함해야 한다.가장 긴 수열을 찾는 프로그램을 작성하시오. 입력첫째 줄에 구간의 수 N이 주어진다. (1 ≤ N ≤ 100,000)다음 N개 줄에는 각 구간 [A,B]의 정보 A와 B가 주어진다. (1 ≤ A  출력첫째 줄에 수열의 길이 K를 출력한다. 다음 K줄에..

문제 링크https://www.acmicpc.net/problem/23035 문제가톨릭대학교에는 많은 고양이가 있다. 고양이를 사랑하는 많은 학생 중 한 명인 쿠기는 수업 시간보다 항상 일찍 등교해서 고양이 밥을 챙겨주곤 했다. 안타깝게도 이제 4학년이 된 쿠기는 취업 준비에 바빠 고양이를 챙기는 것에 많은 시간을 쏟을 수 없게 되었다.그런데도 고양이를 사랑하는 쿠기는 학교 정문에서부터 수업이 있는 다솔관까지 가는 여러 경로 중에, 가장 많은 고양이를 만나 밥을 챙겨 줄 수 있는 경로를 찾고 싶어 한다. 쿠기는 다솔관까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동하는 시간은 1만큼 걸린다. 이때, 고양이에게 밥을 주는 시간은 무시할 수 있을 정도로 짧다. 쿠기는 정문에서 다솔관까지 가장 빠르게..

문제 링크https://www.acmicpc.net/problem/31503  문제이 문제는 DP (Small)과 문제의 수 제한, 질문의 수 제한, 문제의 난이도 제한이 다른 문제이다.DP는 DYNAMIC Porani의 약자이다.DYNAMIC한 포라니는 가능한 문제를 DYNAMIC하게 푸는 것을 좋아한다. DYNAMIC한 문제 풀이란 문제의 번호와 난이도가 모두 증가하도록 가능한 한 많이 푸는 것이다.방학을 맞은 포라니는 알고리즘 능력 향상을 위해 선배로부터 추천 문제 셋을 받았다. 나태한 포라니는 모든 문제를 풀고 싶지 않다. 만약 선배로부터 어떤 문제를 풀라는 지시를 받았을 때, 그 문제를 포함하여 DYNAMIC하게 문제를 풀었을 경우 몇 문제를 풀어야 하는지 알려주자. 입력첫 번째 줄에 문제의 수..

문제 링크https://www.acmicpc.net/problem/2568  문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.  전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 ..

문제 링크https://www.acmicpc.net/problem/14003 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다. 예제 입력 16..

문제 링크https://www.acmicpc.net/problem/21624 문제Donald owns a nice small house in Manhattan. Due to recent elections it is important to protect yourself from the potential public unrest, so Donald has decided to build a fence around his house.Donald's house can be represented as a polygon on the plane, with all the coordinates being integers. Moreover, all of his house corners are exactly 90deg, an..

문제 링크https://www.acmicpc.net/problem/5670 문제휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력해야 한다.길이가 1 이상인 문자열 c1c2...cn이 지금까지 입력되었을 때, 사전 안의 모든 c1c2...cn으로 시작하는 단어가 c1c2..