[동적계획법] 연속합

 

문제

n개의 정수로 이루어진 임의의 수열이 주어진다.

우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.

단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자.

여기서 정답은 12+21인 33이 정답이 된다.

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.

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

 

import java.io.*;
import java.util.*;

public class Main{
    public static int hap=0;
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
            
        }
        for(int i=0;i<n;i++){
            if(hap==0){
                arr[i]=??
            }
        }
        
    }
    public static int sum(int n){
        
    }
    
}

여기까지 끄적여 봤는데 잘 모르겠다...

 

메모이제이션은 이전까지 탐색했던 값과 현재 위치의 값을 비교하여 큰 값을 저장하면 되는 것이다.

 

static int recur(int N) {
 
	// 탐색하지 않은 인덱스라면
	if(dp[N] == null) {
 
		// (이전 배열의 누적합 + 현재 값)과 현재 값을 비교하여 최댓값을 N위치에 저장
		dp[N] = Math.max(recur(N - 1) + arr[N], arr[N]);
		
	}
		
	return dp[N];
}

 

 

 

https://velog.io/@hadoyaji/int와-Integer는-무엇이-다른가

int와 Integer는 무엇이 다른가

int Integer는 무엇이 다른가?.,..

 

 

 

import java.io.*;
import java.util.*;
 
public class Main {
	
	static int[] arr;		// 배열 입력값들이 저장됨
	static Integer[] dp;	// 메모이제이션 할 dp 그 값들의 합들이 저장됨
	static int max;			// 최댓값 변수 
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		arr = new int[N];
		dp = new Integer[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		/*
		 * dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
		 * arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
		 * max또한 첫 번째 원소로 초기화 해준다.
		 */
		dp[0] = arr[0];
		max = arr[0];
		
		// dp의 마지막 index는 N-1이므로 N-1부터 Top-Down 탐색 
		recur(N - 1);
		
		System.out.println(max);
	}
	
	static int recur(int N) {
		
		// 탐색하지 않은 인덱스라면
		if(dp[N] == null) {
			dp[N] = Math.max(recur(N - 1) + arr[N], arr[N]);
 
			// 해당 dp[N]과 max 중 큰 값으로 max 갱신 
			max = Math.max(dp[N], max);
		}
		
		return dp[N];
	}
}

 

어려워지는데 ~ 

이 문제는 실버 2다. 

나는 실버 3정도 되는 듯

반복해서 보자!

 

 

 

 

 

참고 블로그 : https://st-lab.tistory.com/140

[백준] 1912번 : 연속합 - JAVA [자바]