문제에서 옮겨진 번호는 4, 7, 1, 2번이다.3, 5, 6 번은 그대로 있는데, 문제에 주어진 수열의 최장 증가 부분 수열(LIS)로 보인다.N - (LIS 크기)를 하면 옮겨지는 아이의 최소 수를 구할 수 있다.LIS를 구할 수 있는 방법 중 이분 탐색을 사용했다. 구현 1import java.io.*;import java.util.ArrayList;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br..

상자를 넣을 수 있는 조건은 앞 상자 넣을 수 있는 상자의 개수가 최대가 되려면 뒤에 있는 상자 크기는 점점 늘어나야 한다.예제 입력 1 : 1, 2, 3, 5, 6 -> 5예제 입력 2 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 -> 10문제에 주어진 수열에서 최장 증가 부분 수열(LIS)을 구하고 그 개수를 반환해야 한다.최장 증가 부분 수열 (Longest Increasing Subsequence)어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.최장 증가 부분 수열을 구현하는 방법으로는 DP와 이분 탐색이 있다. 구현 1 - DPimport ja..

파도반 수열이라 하니 비슷한 피포나치 수열이 생각난다. 억지피보나치수열에는 패턴이 존재하는데, 파도반 수열 문제에 나열된 숫자들도 어떤 패턴을 가지고 있을 것 같다. 피보나치 수열N = 10 조건을 가지는 피보나치수열을 구한다면 1 + 1 + 2 + 3 + 5 + 8 + 13 + 22 + 35 + 55이다.F(1) = F(2) = 1의 초기값을 가지며 점화식으로 F(n) = F(n-1) + F(n-2)가 된다. 파도반 수열먼저 변의 길이는 생각하지 말고(?) 규칙을 찾기 위한 삼각형을 그려보자.여러 방식으로 그림을 그려봤지만 이 그림에서 규칙을 찾게 되었다.문제의 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 수열에서 보면 4번 삼각형을 그렸을 때 변의 길이가 늘어나기 시작하고,6번 삼각형을 그릴 ..

LDS와 반대인 LIS 알고리즘을 사용하여 푸는 문제이다.LIS - 최장 증가 부분 수열어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.-- 나무위키문제는 가장 긴 부분 수열이 아닌, 증가 부분 수열 중 가장 크게 증가하는 부분 수열의 합을 출력해야 한다. 이전 글인 LDS 문제에서는 최대 길이를 저장했다면, 이번 문제는 최대 합을 저장해야 한다.수열 A11002506035678최대 합1101353113611172432구현import java.io.*;import java.util.StringTokenizer;public class Main { public st..