글 읽기 - 문제 접근 방식이 틀렸나요?

skeep194 4년 전 0

dp[left][right][color] = [left, right] 구간을 color 번호의 색으로 칠한 최소값이라고 정의했습니다.

인풋을 받을 때 연속해서 들어오는 수는 미리 잘라서 -> 1, 1, 1, 2, 2, : 1, 2 로 만들었습니다.

[0, 0, arr[0]], [n-1,n-1,arr[n-1]] 까지 시작 구간으로 정하고 각 구간당 왼쪽 혹은 오른쪽으로 넓히는데 왼쪽으로 갈 경우 현재 색과 같으면 dp(left-1,right,color) 재귀 호출하고 다르면 min(dp(left-1,right,color)+1,dp(left-1,right,arr[left-1]+1) 이렇게 해서 지금 색으로 왼쪽 색을 바꾸거나 왼쪽 색으로 지금 색을 바꾸고 1을 더했습니다.

오른쪽도 왼쪽과 마찬가지로 재귀호출했고 두 구간이 끝에 도달하면 ([0, n-1]) 0을 반환하도록 했습니다.

혹시 이렇게 풀면 아예 반례가 생기는 부분이 있을까요?

int n, k;
vector<int> arr;
int cache[201][201][21];

int dp(int left, int right, int color)
{
    if(left == 0 && right == n-1) return 0;
    int& ret = cache[left][right][color];
    if(ret != -1) return ret;
    ret = INF;
    if(left != 0)
    {
        if(arr[left-1] == color) return ret = dp(left-1,right,color);
        else ret = min({ret, dp(left-1,right,color)+1,dp(left-1,right,arr[left-1])+1});
    }
    if(right != n-1)
    {
        if(arr[right+1] == color) return ret = dp(left,right+1,color);
        else ret = min({ret, dp(left,right+1,color)+1, dp(left,right+1,arr[right+1])+1});
    }
    if(left == right && left != n-1) ret = min(ret, dp(left+1,right+1,arr[left+1])); //0부터 n-1까지 시작하는 구간 변경
    return ret;
}

int main()
{
    fastio;
    cin>>n>>k;
    for(int i=0;i<n;++i)
    {
        int x;
        cin>>x;
        if(arr.empty() || arr.back() != x)
        {
            arr.push_back(x);
        }
    }
    n = arr.size();
    memset(cache,-1,sizeof(cache));
    int ret = dp(0,0,arr[0]);
    cout<<ret;
}

jinhan814 2년 전 0

반례입니다

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

#out
4

#wrong_answer
5

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

문제

문제

출처

ICPC

문제 접근 방식이 틀렸나요?

skeep194 4년 전 0

jinhan814 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말