-

연속합 1912https://www.acmicpc.net/problem/1912 [문제 풀이]dp[i]를 index가 i일때의 연속합이라고 정의하면 dp[i] = max(ar[i], dp[i-1]+ar[i])이런 점화식을 구할 수 있다. 우선 10개의 숫자가 입력됐을 때 방금 구한 점화식으로 연속합을 구해보면index 1 2 3 4 5 6 7 8 9 10 입력 10 -4 3 1 5 6 -35 12 21 -1 연속합10 6 9 10 15 21 -14 12 33 32 표와 같고, 연속합의 최댓값은 index가 9일때 33(12+21)이라는 것을 알 수 있다. 계산을 모두 마친 후, dp배열에 저장된 연속합들 중 가장 큰 값을 출력하면 끝!! 1234567891011121314151617181920212223..

자두나무 2240 https://www.acmicpc.net/problem/2240 [문제 풀이]dp[T][W] 2차배열 생성하고,dp[T][W]는 T초에 W번 이동했을 때 먹은 자두의 개수 라고 했을 때W % 2 == 0일때 dp[i][j] = jadu[i] == 1 ? Math.max(dp[i-1][j-1] + 1, dp[i-1][j]+1) : dp[i-1][j];W % 2 == 1일때 dp[i][j] = jadu[i] == 2 ? Math.max(dp[i-1][j-1] + 1, dp[i-1][j]+1) : dp[i-1][j]; 연산을 마치고 dp[T][0] ~ dp[T][W] 중 최댓값 출력 123456789101112131415161718192021222324252627282930313233343..

1학년 5557https://www.acmicpc.net/problem/5557 [문제 풀이]눈여겨 볼 점은 계산을 하다보면 범위가 int형 범위를 넘어갈 수도 있다는 점.상근이가 아는 수는 다행히 0부터 20까지라는 점이다. 1. 숫자의 개수 N을 입력받고 2. 다음 줄에 나오는 N개의 숫자를 long형 ar[]배열에 집어넣는다. 3. 2차원배열 dp[N+1][21]를 생성한다. 어떻게 풀어나갈 생각이냐면.... dp[i][j]를 'i번째 수 까지 계산을 했을 때 j를 만들 수 있는 경우의 수'로 생각한다. 예를들어, dp[1][8] = 1 (8 = 8) dp[2][5] = 1 (8 - 3 = 5) dp[2][11] = 1 (8 + 3 = 11) 이다. 4. dp[i-1][]와 dp[i][]와의 관계를..