[BOJ/백준] 1912 연속합

● [문제번호 1912] 연속합

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

1912번: 연속합

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

 

● 풀이 과정

: 연속된 부호의 부분 배열을 묶어서 이리저리 해보려했으나 점점 복잡해져서 구글링을 했다.

 

: DP의 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ index까지 범위에서 연속된 몇 개의 수를 선택해서 구할 수 있는 가장 큰 합

 

2. 점화식 찾기

→ (index 수) < (index 수 + 이전 연속 몇 개의 수들) 인 경우

dp[index] = dp[index - 1] + num[index]

 

→ (index 수) >= (index 수 + 이전 연속 몇 개의 수들) 인 경우

dp[index] = num[index]

 

3. 초기값 정하기

→ dp[0] = 입력된 배열[0]

 

● 주의 할 것

: 만약 배열의 index를 1부터 이용하게 되면

0에 위치한 값이 -1000으로 두어야 한다.

하지만 index를 특별하게 활용하지 않으므로 0부터 이용하는 코드로 작성하였다.

 

● 참고 할 것

: 풀이과정 참고

https://mtoc.tistory.com/41

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// num : 입력 배열
// dp : index까지 범위에서 연속된 몇 개의 수를 선택해서 구할 수 있는 가장 큰 합
vector<int> num, dp;
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    num.assign(N, 0);
    // -1000 : 원소 중 가장 작은 값
    dp.assign(N, -1000);
    
    // 입력
    for(int n = 0; n < N; n++)
        cin >> num[n];
    
    // Bottom - Up
    dp[0] = num[0];
    for(int n = 1; n < N; n++)
    {
        // (index 수) < (index 수 + 이전 연속 몇 개의 수들) 인 경우
        if(num[n] < dp[n - 1] + num[n])
            dp[n] = dp[n - 1] + num[n];
        // (index 수) >= (index 수 + 이전 연속 몇 개의 수들) 인 경우
        else
            dp[n] = num[n];
    }
    
    // 최댓값 출력
    cout << *max_element(dp.begin(), dp.end());
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212