![]()
13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다) 풀이 이 문제의 키 포인트는 자신을 포함한 n개의 수열에서의 최댓값을 구하는 배열을 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 구한다. 이때, left[i-1] + right[i+1]은 i번째의 수를 뺀 값이라는 것..
![]()
10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 풀이 계단수는 이전 자리의 수에서 +1 혹은 -1한 수가 현재 자리에 올 수 있는 수를 말한다. 따라서 이전 자리 수에 따라서 그 다음에 오는 수에 영향을 끼친다. 따라서 이를 활용하여 DP배열을 만들고 문제를 풀었다. 먼저 첫 번째 자리에 오는 수를 생각해보자. 첫 번째 자리에 올 수 있는 수는 1 ~ 9까지 총 1개의 경우의 수밖에 없다. 즉, D[1][i] = 1이 된다. (D[1][0] = 0, 계단수에서 첫 번째 자리에 0이 올 수 없다.) 여기서 1자리가..
