[백준] 1912_연속합 (JAVA)

1. 문제

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

1912번: 연속합

---

 

 

2. 문제 풀이 겸 회고

나 진짜 DP... 못하는데......

하지만 포기하지 않는다... DP.. 단계별로 풀어보고 있지만.. 이번 dp는  처음으로 타 블로그 참고하지 않고

혼자 힘으로 해결해 나갔다는 그러한 이야기... 진짜 뿌듯.... (대견해 이숨)

나는 DP 풀 때 점화식보다는 규칙을 찾는 것 같다.. 이거 맞는지 모르겠는데... ㅠㅠㅠㅠ

 

규칙을 찾았다!!!...

연속되면서 가장 큰 수를 찾는 건데.. 

연속된 누적합 구하고 음수가 나오면 다시 처음부터 계산해주기

 

예시를 들어보면

2    3   -1   3    7    3    9  14   9  10   -> DP 배열로 따로 관리..

이렇게 dp 배열에 값을 저장하면서 계산해주면 된다.

dp[i] = dp[i-1] + num[i]   해줘서 dp값을 차곡차곡 쌓아준다.

하지만

dp[i-1] <  0 

dp는 연속된 합의 값이니깐  음수일 경우는 굳이 필요 없고 값만 더 낮추는 것이기 때문에 리셋 (num값 다시 데려오기)

dp[i] = num[i]   현재부터 다시 시작 

이런 식으로 값 구해줘서 

dp 배열에서 가장 큰 값 찾아주면 끗~~~~~~~~~~

 

 

 

3. 코드

package net.acmicpc.solution;

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


public class Solution_1912_연속합 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < num.length; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}

		int[] dp = new int[N];
		dp[0] = num[0];


		for (int i = 1; i < num.length; i++) {
			if (dp[i - 1] < 0) {
				dp[i] = num[i];
			} else {
				dp[i] = dp[i - 1] + num[i];
			}
		}

		//System.out.println(Arrays.toString(dp));
		int max = num[0];
		for (int i = 1; i < dp.length; i++) {
			max = Math.max(dp[i], max);

		}
		System.out.println(max);

	}
}

 

 

 

피드백은 언제나 환영입니다 :) 🌳