[백준/C,C++] 11053번: 가장 긴 증가하는 부분 수열
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) 알고리즘이라고 하더라구요. 로직 자체는 크게 어렵지 않습니다. 100, 200, 300, 10, 20, 30, 1, 2, 400이라는 수열이 있다고 가정해보겠습니다. 1 2 3 4 5 6 7 8 9 100..
2021. 3. 8.
[백준/C,C++] 10844번: 쉬운 계단 수
www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1자리에 해당하는 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9입니다. 2자리에 해당하는 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98입니다. 즉, 1 뒤에 올 수 있는 숫자가 2개, 2 뒤에 올 수 있는 숫자가 2개 이런 식으로 붙어 약 2배씩 늘어납니다. 1의 경우엔 0과 2, 2의 경우엔 1, 3 이런 식이죠. 그래서 2자리에 해당하는 계단 수중 다시 0으로 끝나는 수는 1로 끝나는 1자리 계단 수의 개수와 같고, 1로 끝나는..
2021. 3. 8.