Baekjoon/[3] DP

[백준] 1912번 연속합 JAVA (자바) 풀이

Poorm 푸름 2024. 6. 30. 22:01

문제 1912번 (DP)

 :  n개의 정수로 이루어진 임의의 수열

    연속된 몇 개의 수를 선택해서 가장 큰 합을 구해라 (1개 이상 선택)

 

    예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열일 때 답은 12+21인 33이다

 

 

[입력]


 :  첫째 줄에 정수 n(1 ≤ n ≤ 100,000)

    둘째 줄에는 n개의 정수로 이루어진 수열

    (수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수)

 

 

[출력]

 

 :  첫째 줄에 답을 출력

 


[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)  보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결 작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization) 타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때 모두 계산해야 답이 나올 때
재귀 반복문
시간 복잡도 O(n) 시간 복잡도 O(n)

 

1. dp 배열 말고도 수열을 저장할 배열이 필요

  • 계단 오르기 문제처럼 배열이 하나 더 필요하다
  • 각 dp 배열에 arr값을 추가한다

 

2. max 값을 두단계에 걸쳐 계산해라

  • 1단계 현재값에서 선택 시작 VS 이전값을 포함해 현재값 선택
    • dp는 단순히 해당 지점의 값이 아닌 그 값까지 오기까지 최적의 결과를 저장한 것

    • 현재값에서 선택 시작 = arr[i] 해당 인덱스에서부터 시작
    • 이전값을 포함해 현재값 선택 = dp[i-1] + arr[i]
      이전값은 어디서부터 어디까지인지는 자세히 알 수 없다 
      예를들어 1,2,3이 이전 인덱스라고 치면 1부터 연속해서 택했을지
      2부터 연속해서 택했을지 3부터 택했을지는 모른다
      다만 아주 작은 인덱스부터 순차적으로 이전+현재의 연속된 모든 값이 최대인지
      현재부터 시작하는게 최대인지 계산해왔기 때문에 dp를 사용하면 해결된다
  • 2단계 최종 dp 배열에서 최대값 뽑기
    • 각각의 지점에서 최적의 결과를 dp에 저장해왔다 몇개의 지점을 택할지는 자율이므로
      dp 중에서 max값을 한번더 계산한다

 

3. 인덱스 예외처리 발생

  • result를 dp[0] 또는 arr[0]으로 초기화한다

 

 

 [코드]

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));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];
        int dp[] = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        dp[0] = arr[0];
        int result = dp[0];
        
        for(int i=1;i<N;i++){
            dp[i]=Math.max(dp[i-1]+arr[i],arr[i]);
            
            result = Math.max(dp[i], result);
        }
        
        
        System.out.println(result);
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int dp[] = new int[1000001];  dp 배열 초기화

    int arr[] = new int[N];
        
 :  StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken()); 
    }
        
 :  dp[0] = arr[0];  dp배열 0번 인덱스 초기화
    int result = dp[0];  출력할 결과 dp[0]으로 초기화
        
  :  for(int i=1;i<N;i++){  1부터 시작
            dp[i]=Math.max(dp[i-1]+arr[i],arr[i]);  [누적값+현재값]과 현재값 중에 최대값 뽑기
            
            result = Math.max(dp[i], result);  최적의 값만 저장한 dp 배열 중 최대값 뽑기
     }


 :  System.out.println(result);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)



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

 

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시