Algorithm, boj, 1912(연속된 숫자), dp
DP(다이나믹 프로그래밍)
- 주어진 문제를 여러 개의 부분문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다
- dp는 겹치는 문제가 발생하기 때문에 메모제이션 등이 필요하다
- 큰 문제의 작은 부분은 항상 최적이다
문제 풀이
: n번째 숫자일때는 두가지 경우가 있다
- 현재 수와 직전의 수를 더하거나
- 직전의 수를 더하지 않거나 이때, 직전의 수는 항상 최적이므로 dp[n-1] 이라고 보면된다. amount[i] = Math.max(numbers[i]+amount[i-1], numbers[i]); ```java package org.baekjoon; import java.util.Scanner;
public class test1912_numbers {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
int[] numbers = new int[size];
for(int i=0; i<size; i++)
numbers[i] = sc.nextInt();
System.out.println(find(numbers, size));
}
static int find(int[] numbers, int size) {
int[] amount = new int[size];
amount[0] = numbers[0];
int max = amount[0];
if (size == 1)
return max;
for (int i=1; i<size; i++) {
amount[i] = Math.max(numbers[i]+amount[i-1], numbers[i]);
if (amount[i] > max)
max = amount[i];
}
return max;
}
} ```