Algorithm, boj, 1912(연속된 숫자), dp

DP(다이나믹 프로그래밍)

• 주어진 문제를 여러 개의 부분문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다
• dp는 겹치는 문제가 발생하기 때문에 메모제이션 등이 필요하다
  
• 큰 문제의 작은 부분은 항상 최적이다

문제 풀이

: n번째 숫자일때는 두가지 경우가 있다

1. 현재 수와 직전의 수를 더하거나
2. 직전의 수를 더하지 않거나 이때, 직전의 수는 항상 최적이므로 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;
}

} ```

---

Reference

문제바로가기