보단잉의 블로그

문제 링크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 알고리즘 분류다이나믹 프로..