[BAEKJOON] 1912 연속합

문제 요악

• 알고리즘 분류: 동적 계획법
• 난이도: Silver2
• 문제 요약
  • 배열을 주어졌을때 연속된 수가 합한 값중에 최대 값을 구해라
• 사이트 주소: https://www.acmicpc.net/problem/1912

9184번: 신나는 함수 실행

문제 풀이

동적 계획법 관련 내용은 아래 사이트에 참조 하면된다.

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키

 배열의 데이터가 10,000,000 이고 시간 제한도 1초라서  O(n)으로 풀어야 한다.

n = int(input())
array = list(map(int, input().split()))

max_value = array[0]

for i in range(n):
    for j in range(i+1, n+1):
        max_value = max(max_value, sum(array[i:j]))
print(max_value)

 위 코드 방식으로 하면 정답은 맞지만 O(n^2) 시간 만큼 걸려서 시간 초과가 나올것이다. 그래서 DP 방법으로 풀어야 한다.

문제 접근 방법

 동적계획법은 대부분 규칙, 패턴만 잡으면 코드 작성은 몇줄이 안나온다. 그래서 이번 문제도 규칙만 알면 쉽다. 하지만 그 규칙 보는게 힘들어서 문제지만....

10 -4 3 1 5 6 -35 12 21 -1

10 max(-4, -4 + 10) 3 1 5 6 -35 12 21 -1 → 10 6 3 1 5 6 -35 12 21 -1

 위에 첫번째 예제이다. 그리고 인덱스를 1번방부터 탐색해서 뒤에 10하고 -4 더하면 6이 나온다. 그래서 첫번째 인덱스는 -4 6 중 6이 더 크므로 6을 저장한다.  그 다음에 두째방도 두번째 인덱스 값과 첫번째 인덱스를 더한 값이랑 비교 해서 더 큰 숫자를 저장하면된다. 

2 - 10 6 9 1 5 6 -35 12 21 -1
3 - 10 6 9 10 5 6 -35 12 21 -1
4 - 10 6 9 10 15 6 -35 12 21 -1
5 - 10 6 9 10 15 21 -35 12 21 -1
6 - 10 6 9 10 15 6 -14 12 21 -1
7 - 10 6 9 10 15 6 -14 12 21 -1
8 - 10 6 9 10 15 6 -14 12 33 -1
9 - 10 6 9 10 15 6 -14 12 33 32

위와 같이 탐색이 끝나면 배열중 가장 큰값을 불려오면된다.

 

Code

Python

n = int(input())
array = list(map(int, input().split()))

for i in range(1, n):
    array[i] = max(array[i], array[i] + array[i-1])
print(max(array))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] array = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 1; i < n; i++) {
			array[i] = Math.max(array[i], array[i - 1] + array[i]); 
		}
		
		System.out.println(Arrays.stream(array).max().getAsInt());
	}
			
}