매일 조금씩

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP문제로, Index를 차례대로 증가시키면서 해당 Index 왼편에 올 수 있는 바이토닉 부분 수열의 최대 개수를 구한다. 이때 기준 Index에서 작은 Index를 체크하면서, 기준보다 작은 수의 바이토닉 수열 최대 개수 중에 최대 값을 구한 후 +1을 해주면 된다. 아래 문제의 왼쪽 편만 구한 것이다. ..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 기준 숫자에서 왼쪽과 오른쪽을 나눈다. left[i] = i번째 수의 왼편에 올 수 있는 오름차순 부분 수열의 최대 개수 right[i] = i번째 수의 오른편에 올 수 있는 내림차순 부분 수열의 최대 개수 left[i] + right[i] 의 최대값에 1을 더한 것이 답이 된다. (1을 더하는 이유는 left, right에 기준 숫자가 빠져있기 때문) 차례대로 index를 증가 또는 감소 시키면서 채워나..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP문제가 제일 어렵다. DP문제는 사고의 전환이 필요하다. 나한테 너무 어려운 부분... 어쨌든 해당 문제는 구글링을 통해 힌트를 조금 얻어서 풀었다. dp[i][j] = i자리수에서 j로 끝나는 계단수의 개수 N(자리수)가 1일 때 1, 2, 3, 4, 5, 6, 7, 8, 9 dp[1][0] = 0 dp[1][1] = 1, dp[1][2] = 1 ... dp[1][8] =1 dp[1][9] = 1 N이 2일 때 10 / dp[2][0] = 1 21 / dp[2][1] = 1 12, 32, / d..