[Java] BOJ11053_가장 긴 증가하는 부분 수열
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 제목 그대로 최장 증가 부분 수열 문제이다. N의 범위가 1000으로 작기 때문에 단순 이중 포문으로도 구현 가능하다. DP[i]는 i번째 수를 마지막 원소로 가지는 수열의 길이를 의미한다. i번째 이전의 수들을 j번째 수라고 하면 i번째 수가 j번째 수보다 크고 현재 수열의 길이가 dp[j]+1보다 작다면 dp[i]를 업데이트..
[Java] BOJ10844_쉬운 계단 수
www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 출력 조건에서 값이 매우 크기 때문에 브루트 포스로는 할 수 없다는 것을 알았고, 이전 자리까지의 수가 다음 자리의 수를 결정하기 때문에 DP라는 것을 유추할 수 있었다. N자리 수에서 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 맨 끝에 몇 개 올 수 있는지에 대하여 DP 배열을 구성했다. 주의할 점은 0은 1번째자리에서 존재할 수 없고, 이전 수는 오직 1뿐만이 가능하다. 9는 8뿐만이 가능하다. 0과 9는 서로 계단 수가 아니다. 나머지 수는 자신보다 큰 값이나 작은 값 다음에 올 수 있다. *시도는 안해봤지만..
