글 읽기 - 혹시 이런식으로 접근했을때 나오는 문제점이나. 반례를 알고 싶습니다.

timeslump 3년 전 0

이렇게 dp로 풀면 어떠한 문제가 생기나요? 딱히 문제가 없을거 같아서

이렇게 했는데 어떤 점에서 문제인지 모르겠네요

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int InputNum, Color;
    cin >> InputNum >> Color;
    int n;
    int InputArr[200] = {0, };
    int dp[200];
    for(int i = 0; i < 200; i++)
        dp[i] = 300;
    for(int i = 0; i < InputNum; i++)
        cin >> InputArr[i];
    dp[0] = 0;
    for(int i = 1; i < InputNum; i++){
        if(InputArr[i - 1] == InputArr[i])
            dp[i] = dp[i - 1];
        else {
            int Min = dp[i - 1] + 1;
            for (int j = 0; j < i; j++) {
                if (InputArr[i] == InputArr[j]) {
                    if (dp[i - 1] - dp[j + 1] + 1 + dp[j] <= Min)
                        Min = dp[i - 1] - dp[j + 1] + 1 + dp[j];
                }
            }
            dp[i] = Min;
        }
    }

    cout << dp[InputNum - 1] << endl;
}

jinhan814 2년 전 1

반례입니다

#in
9 3
1 2 3 2 1 2 3 2 1

#out
4

#wrong_answer
3

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

문제

문제

출처

ICPC

혹시 이런식으로 접근했을때 나오는 문제점이나. 반례를 알고 싶습니다.

timeslump 3년 전 0

jinhan814 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말