![]()
2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 의식의 흐름 이전에 풀었던 가장 긴 증가하는 수열(https://monicajo074.tistory.com/44)을 사용하면 될 것 같은뎅..? 일단 가장 긴 증가하는 수열을 구한 다음에 해당 수열 안에 들어가지 못한 아이들만 옮기면 그게 최소인 경우일 것 같다. 풀이 과정 1. 아이들의 수(N)을 입력 받는다. 2. 현재 서있는 순서를 배열(nums)에 담고 증가하는 수열의 길이를 담을 배열(dp)를 1로 초기화한다. for(int i=0;i 자세한 풀이는 2023...
![]()
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net > 의식의 흐름 수열의 크기가 최대 1,000이니까 O(N^2) 가능하겠넹..? 그럼 전체 다 훑어봐야지~ > 풀이 과정 1. 수열의 크기(N)을 입력 받는다. 2. 수열을 배열(nums)에 입력받고 수열의 길이를 저장하는 배열(arrCnt)를 1로 초기화한다. 3. nums[i]와 뒤쪽 수(nums[j])를 비교한다 - 만약 nums[i] arrCnt[i]+1인 경우, 가장 긴 수열을..
