문제 링크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/2352 문제반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오 입력첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …,..

문제 링크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/2550  문제N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.  하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이..

문제 링크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/12738 문제수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1610 20 10 30 20 50예제 출력 14 알고리즘 분류다이나믹 프로..

문제 링크https://www.acmicpc.net/problem/23563 문제루시우는 높이가 H이고 너비가 W인 맵의 시작점에서 끝점까지 이동하려고 한다.맵은 H개의 행과 W개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다.루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다.루시우가 한 칸을 이동하는 데에는 1초가 걸린다.하지만 루시우가 벽을 타고 이동하면 순식간에 (0초의 시간에) 상, 하, 좌, 우 방향 인접한 칸으로 이동할 수 있다.어떤 빈칸의 상하좌우 중 하나가 벽이면 이 칸은 벽에 인접한 칸이라고 한다.벽에 인접한 칸에서 벽에 인접한 칸으로 이동하면 벽을 타고 이동한다고 말한다. 루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리..

문제 링크https://www.acmicpc.net/problem/32188 문제포탈 게임은 직선 위에서 진행되는 게임이다. 직선에는 0부터 N − 1까지의 번호가 매겨진 N개의 칸이 존재한다. 게임의 목표는 0번 칸에서 출발해 N − 1번 칸에 가능한 한 빠르게 도착하는 것이다.이 게임에는 포탈이 총 C개 존재하며, 포탈은 레드 포탈과 블루 포탈로 총 두 종류가 있다. 각 칸에는 포탈의 시작 지점이 최대 1개 존재할 수 있다. 시작 지점이 ai번 칸에 있는 포탈을 이용하면, 해당 포탈의 끝 지점인 bi번 칸으로 이동하게 된다. 포탈은 시작 지점에서 끝 지점으로만 이동할 수 있기 때문에 동일한 포탈을 이용해 bi번 칸에서 ai번 칸으로는 이동할 수 없다.포탈 게임에서는 N − 1번 칸에 도착하기 전까지 ..

문제 링크https://www.acmicpc.net/problem/32177 문제2차원 평면상에 살고 있는 푸앙이는 신입생으로 대학에 입학하게 되었다. 대학에 입학한 푸앙이는 활발한 성격으로 N명의 친구들을 사귀었고, 친구들을 1번, 2번, ⋯, N번으로 부르려고 한다.푸앙이는 그중 몇몇 친구들과 함께 사진을 찍게 되었다. 친구들에게 찍은 사진을 받고 싶지만 움직이기 귀찮은 푸앙이는 이 사진들을 가만히 앉아서 에어드롭으로 받으려고 한다.에어드롭은 보내는 휴대폰과 받는 휴대폰 사이의 버전 차이가 T 이하이면서 유클리드 거리로 최대 K만큼 떨어진 거리의 기기에만 사진을 전송할 수 있으며, 푸앙이와 사진을 가지고 있었던 친구의 휴대폰 버전 차이가 T보다 크더라도 다른 친구들을 이용한 간접적인 경로가 있다면 사..

문제 링크https://www.acmicpc.net/problem/14622 문제인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있는 능력을 가지게 되었다. 인하대학교에 소수의 신이 있다는 소문이 퍼지자 인상대학교의 소수 마스터 규성이는 대웅이에게 도전장을 내밀었다.둘은 누가 더 소수를 사랑하는지 내기를 하기로 하였다.하지만 누가 더 소수를 사랑하는지에 대한 기준이 없으므로 소수 게임을 이용하기로 하였다.소수게임의 규칙은 다음과 같다.  두 사람이 번갈아가며 소수를 말한다.소수가 아닌 수를 부르게 될 경우 상대방은 지금까지 상대방이 말한 소수중에서 3번째로 큰 수만큼 점수를..

문제 링크https://www.acmicpc.net/problem/32339 문제세종이는 조선 시대의 지도인 대동여지도를 보면서 한양을 포함한 모든 지역을 연결하는 도로를 설치한다면 비용이 얼마나 들지 궁금해졌다.설치할 수 있는 도로의 종류는 총 3가지로 도보 전용 도로, 말 전용 도로, 마차 전용 도로가 있다.세종이는 지역을 연결할 수 있는 모든 도로를 전부 설치하고 싶지만 국고가 부족한 관계로 최소한의 비용을 사용하여 모든 지역을 이동할 수 있도록 도로를 설치하려 한다. 만약 최소한의 비용으로 도로를 설치할 수 있는 경우가 여러가지라면, 조정에서 지정해준 우선순위가 1번째인 도로가 가장 많은 순으로, 이 경우도 여러가지라면 우선순위가 2번째인 도로가 가장 많은 순으로 설치하려 한다.세종이를 도와 최소..