공부 130일차: 백준 1912번 연속합 자바 java

1912 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

 

 

 

---

백준 1912번 문제 연속합

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

처음 접근은 주어진 예제에서 처음부터 끝까지 쭉 더해보는 배열을 하나 구해보는 것이었다

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	-2	19	18

그러자 빨간색으로 표시한 부분이 정답이 되는 부분이라,

지금까지를 쭉 더하는 것이 아니라 새로 시작, 즉 12를 앞의 수에 더하는 것이 아니라 그대로 사용해야 했다

따라서 저 지점 같은 상황이 생길 때, Math.max() 함수를 이용해 선택할 수 있게끔 해야 했다

 

10	-4	3	1	5	6	-35	12	21	-1
arr[i] : 10 dp[i-1] + arr[i] : x (dp[-1]은 존재하지 않음)	-4 6	3 9	1 10	5 15	6 21	-35 -14	12 -2	21 33	-1 32

그럼 이렇게 나오게 된다

 

이후 dp를 순서대로 배열하여 가장 큰 수를 출력하면 되는 문제다

dp는 앞서 구한 것에서 뒤를 구하도록 하는 방식이 많다는 것을 잊지 말기!

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        
        int[] arr = new int[n];
        int[] dp = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // dp[-1]이 없으므로 dp[0]은 arr[0]값으로 초기화
        dp[0] = arr[0];
        for(int i = 1; i < n; i++) {
            // dp는 dp[i]를 구할 때 dp[i-1]을 이용하는 경우가 많다
            dp[i] = Math.max(dp[i-1]+arr[i], arr[i]);
        }
        
        // 오름차순 정렬
        Arrays.sort(dp);
        System.out.println(dp[n-1]);
 
    }
 
}
 

 

과정 설명에 적은 그대로 구현한 코드이다

 

 

---