문제 푼 날짜 : 2021-10-13

문제

문제 링크 : https://www.acmicpc.net/problem/10211

접근 및 풀이

다이나믹 프로그래밍으로 풀 수 있는 문제였다.

처음에 완전탐색으로 풀려고 했으나, 시간초과가 뜰 것 같아서 DP문제라는 것을 깨닫고 점화식을 찾다가, 결국 찾지 못하고 다른 분의 풀이를 보게 되었다.ㅠ

코드는 아래의 점화식을 이용하여 구현하였다.

dp[i] = max(0, dp[i - 1]) + arr[i]

코드

// 백준 10211번 : Maximum Subarray
#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    
    while (T--) {
        int N, arr[1001];
        cin >> N;

        int sum = 0, ans = -1e8;
        for (int i = 0, num; i < N; i++) {
            cin >> num;
            sum = max(0, sum) + num;
            ans = max(ans, sum);
        }
        cout << ans << '\n';
    }
    return 0;
}

결과

피드백

생각보다 간단한 점화식이어서 좀 더 고민할 걸 싶었다...
역시 세상엔 고수들이 많고, 나는 아직 갈 길이 멀었다.