시간 제한메모리 제한2초512MB문제성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다. 배열의 길이는 N이다.배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.배열에서 연속한 수가 A와 B일 때, A 예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000) 출력첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이성관이가 좋아하는 배열의 세 번째 조건을 그대로 사용하지 않고 부정을 취하는 것이..

최장 증가 부분 수열 - 나무위키 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. namu.wiki 1. 최장 증가 부분 수열(LIS) LIS 문제를 처음 봤을 때 만능 문제해결 툴 브루트포스를 떠올렸는데 당연히 죽음뿐. LIS 문제의 정해는 보통 두 가지다. O(N2)으로 해결할 수 있는 다이나믹 프로그래밍, O(NlogN)으로 해결할 수 있는 이진 탐색이다. 여기서 또 이진 탐색 해법이 있다는 걸 처음 알았을 때는 "대체 이게 뭔소리냐" 싶었는데 잘 살펴보고 직접 구현해보면 그렇게 어려운 개념은 아니다. 하지만 이 문제를 이미 몇 년 전에 처음 접해서 풀었던 ..