글 읽기 - [C++17] 제출하자마자 틀립니다..!

rbstj0311 2년 전 1

질문 게시판에 있는 반례들 넣어봐도 다 맞는데, 어디서 로직이 틀린 걸까요?

고수님들 도와주십쇼 ㅠㅠ

#include <bits/stdc++.h>
#include <limits.h>

using namespace std;

const int MAX_LEN = 1000;
int N;
int A[MAX_LEN + 1], dp[MAX_LEN + 1];
int max_dp = INT_MIN;

void Input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
}

void InitDP() {
    for (int i = 1; i <= N; i++) {
        dp[i] = 0;
    }
}
void BottomUp() {
    InitDP();
    dp[1] = A[1];
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (A[j] > A[i]) continue;
            dp[i] = dp[j] > dp[i] ? dp[j] : dp[i];
        }
        dp[i] += A[i];
    }
}

void Solve() {
    Input();
    BottomUp();
    for (int i = 1; i <= N; i++) {
        if (dp[i] > max_dp) max_dp = dp[i];
    }
    cout << max_dp << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
    return 0;
}

cchccc 2년 전 1

A[j] == A[i]인 경우에도 dp[i]가 갱신됩니다

rbstj0311 2년 전 0

감사합니다! 말씀하신 부분 수정하니 해결됐습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++17] 제출하자마자 틀립니다..!

rbstj0311 2년 전 1

cchccc 2년 전 1

rbstj0311 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말