BaekJoon_1912 (연속합)

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

1912번: 연속합

 

문제풀이

동적 계획법 개념을 적용하여 문제를 풀 수 있습니다.

연속된 수 끼리만 더할 수 있는 조건을 놓치면 안됩니다!

 

빈 배열(dp)을 하나 만들고, 반복문을 돌면서

입력값을 dp에 먼저 넣은 뒤에

입력값과 dp의 이전값 + 입력값을 비교하여 dp의 이전값 + 입력값이 더 크면 더하여 dp의 해당 index 값을 바꾸면 됩니다.

 

소스코드

/*
연속된 수 끼리만 더할 수 있다.
list 이번값과 dp 이전값을 더하였을 때 dp의 이전값보다 크면 더하는 방식을 반복하여 연속된 수 사이에서 계속 더하기를 반복해 나간다.
*/

const answer = ([n,data]) => {
    const list = data.split(' ').map(Number);

    const dp = [];
    for (let index = 0; index < Number(n); index++) {
        dp[index] = list[index]

        if(dp[index] < dp[index-1] + list[index]){
            dp[index] = dp[index-1] + list[index]
        }
    }

    console.log(Math.max(...dp))

}

const input = [];
require('readline').createInterface(process.stdin, process.stdout).on('line', (line) => {
    input.push(line);
}).on('close', () => {
    answer(input);
    process.exit();
})

 

소스코드는 gitHub에서도 확인 할 수 있습니다🤗

https://github.com/duduchi/Algorithm/blob/main/Dynamic/BaekJoon_1912.js

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.