본문 바로가기
카테고리 없음

백준 1912 연속합

by 김선지 2024. 4. 15.

 

dp 문제라고는 하는데 약간 포인터 느낌이 나게 풀었다. memo를 쓰니까 이것도 dp의 일종인가??

이게 제일 효율적인 것 같은데 만약에 여기서 dp를 쓴다고 하면 dp[i] = Math.max(dp[i-1], dp[i-1] + input[i]);가 되려나..?   (좀만 생각해봤는데 이거 안된다.)

 

 푸는 방식은 이렇다.

1. sum과 max를 두고 그대로 input을 받는다.

2. 만약에 sum이 max를 넘으면 max에 할당한다.

 

 

시도는 다음과 같다.

1. input에서 -가 나오면  sum에 0을 할당한다. (실패)

     input이 -가 나왔다고 해도 지금까지의 sum 값이 양수면 그대로 가져가는 것이 최대값이기 때문에 반례가 존재한다.

 

2. input값을 모두 sum에 넣고 만약 sum이 음수가 되면 그때 sum에 0을 할당한다. (성공) 

package programers;

import java.util.Scanner;

public class BOJ1912_연속합 {
    public static void main(String[] args) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i < n; i++) {
            int num = sc.nextInt();
            sum += num;
            max = Math.max(max, sum);
            if(sum< 0) {
                sum = 0;
            }

        }
        System.out.println(max);
    }
}