JUINTINATION

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 두 전봇대 a와 b 사이에 설치된 전깃줄 중에 몇 개의 전깃줄을 없애 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제로 LIS(Longest Increasing Subsequence)를 응용하여 해결했습니다. 코드 자바 탑다운 방식을 이용한 코드입니다. poleA 배열은 전봇대 a에 설치된 전깃줄의 위치를 의미하며 arr 배열은 임의의 수 x..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 11053번과 11722번 문제에서 사용했던 LIS(Longest Increasing Subsequence)와 LDS(Longest Decreasing Subsequence)를 동시에 사용해서 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족하는 바이토닉 수열 중 가장 긴 수열의 길이를 구하는 문제입니다. 예를 들어, {10, 2..

문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 14002번 문제를 응용한 문제로 LIS(Longest Increasing Subsequence)를, 즉 어떤 수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 이때 수열이 여러 가지가 될 수 있는 경우에는 아무거나 출력합니다. 예를 들어, 수열 A = {10, 20, 10, 30, 2..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 LIS(Longest Increasing Subsequence)를 구하는 문제로 어떤 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30,..