[코딩테스트]백준 - 연속합

연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

33

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5
-1 -2 -3 -4 -5

예제 출력 3

-1

출처

• 데이터를 추가한 사람: djm03178 dohyeokkim doju jh05013 kimdr123 seedkin
• 빠진 조건을 찾은 사람: isac322 Qwaz
• 문제의 오타를 찾은 사람: jh05013
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 다이나믹 프로그래밍
• 수학

해결한 코드

function successiveSum(){
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().split('\n');
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
    var n = parseInt(input[0])
    var successive = input[1].split(' ')
    for(var i=0; i<n; i++){
        successive[i] = successive[i]/1
    }
    var d = Array(n)
    d[0] = successive[0]
    var max = 0
    for(var i=1; i<n; i++){
        max = Math.max(d[i-1]+successive[i], successive[i])
        d[i] = max
    }
    console.log(Math.max.apply(null,d))
}

successiveSum()

알고리즘

※ 다이나믹 프로그래밍으로 푼다.

1. 초기값을 정한다.

수열의 첫 숫자는 (첫번째 숫자이기 떄문에) 앞에서 연속하여 합할 수 있는 값이 없다.
따라서 무조건 최대가 될 수 있는 합은 자기 자신이다.
초기값을 이와같이 설정할 수 있다.

successive = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]
d[0] = successive[0]

2. 점화식을 세운다.

2-1. 수열의 2번째 숫자의 경우 연속합의 값이 최대가 될 수 있는 경우는 다음과 같이 생각해볼 수 있다.

1번부터~나(2번)까지의 합 vs 나부터 시작해서 나까지의 합(자기 자신)

둘 중에 더 큰값이 2번째 숫자의 최대 연속합이다.

2-2. 수열의 3번째 숫자는?

2번째 숫자의 최대 연속합 + 나 vs 나부터 시작해서 나까지의 합(자기 자신)

둘 중에 더 큰값이 3번째 숫자의 최대 연속합이다.

규칙이 보이는 것 같다.
즉, 현재 순서의 숫자에 대한 최대 연속합은 앞 숫자가 가진 최대 연속합 + 나 vs 나 자신 중 더 큰값이 된다.
이를 다음과 같은 점화식으로 표현할 수 있다.

n = 현재 순서 
d[n] = max(d[n-1] + successive[n], successive[n])

3. 배열 d에 저장된 최대 연속합 중 최댓값을 출력한다.

다이나믹 프로그래밍으로 접근해야 하는 문제인 줄 모르고 처음에는 이중 for문으로 접근했다.
답은 맞는것 같다. 다만 시간초과를 면치 못한..

(시간초과 뜬) 첫 코드

function successiveSum(){
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().split('\n');
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
    var n = parseInt(input[0])
    var successive = input[1].split(' ')
    for(var i=0; i<n; i++){
        successive[i] = successive[i]/1
    }
    var d = Array(n)
    var max = 0
    var sum = 0
    for(var i=0; i<n; i++){
        var curr = successive[i]
        max = 0
        sum = curr
        for(var j=i+1; j<n; j++){
            sum += successive[j]
            if(sum>max){
                max = sum
            }
        }
        d[i] = max
    }
    
    console.log(Math.max.apply(null, d))
}

successiveSum()

이렇게 이중 루프를 사용하면 무조건 틀린다.
이 문제의 시간제한이 1초이기 때문이다.

(해결한 코드와 비슷하지만) 틀린 코드

function successiveSum(){
    var fs = require('fs');
    var input = fs.readFileSync('/dev/stdin').toString().split('\n');
    // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
    var n = parseInt(input[0])
    var successive = input[1].split(' ')
    for(var i=0; i<n; i++){
        successive[i] = successive[i]/1
    }
    var d = Array(n)
    d[0] = successive[0]
    d[1] = Math.max(d[0]+successive[1], successive[1])
    for(var i=2; i<n; i++){
        d[i] = Math.max(d[i-1]+successive[i], successive[i])
    }
    console.log(Math.max.apply(null,d))
}

successiveSum()

이건 왜 틀렸는지 모르겠다.
다른 부분은

d[1] = Math.max(d[0]+successive[1], successive[1])

를 for문에서 시작하지 않은 것 정도..?

해결한 코드에서는 Math.max(d[i-1]+successive[i], successive[i]) 값을 변수 max에 담아 d[i]에 넣었지만, 이게 과연 큰 의미가 있을까 싶다. 똑같은 거 아닌가.. 쩝😓