글 읽기 - 전구 문제 질문드려요

tols91 7년 전 0

1) 그 전 색과 현재색이 같을 때 다음으로 진행

2) 1)이 아니고 그 전 색이 원하는 색일때 다음으로 진행

3) 그 전 색과 현재색이 다를 때 그 전 색을 바꿔주거나 현재색을 바꿔줌 , 값 + 1

이렇게 3가지 경우로 나누었는데 어떤다른경우가있을까요..?

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 987654321

using namespace std;

int n, k;
int arr[213];
int dp[25][213][25];

int solve(int prev, int now, int color)
{
    if(now == n+1) {
            if(prev == color)
                return 0;
            else
                return 1;
    }

    int &ret = dp[prev+1][now][color];
    if(ret != -1) return ret;
    ret = MAX;

    if(prev == arr[now]) {
        ret = min(ret, solve(prev, now+1, color));
    }
    else{
        if(prev == color || prev == -1){
            ret = min(ret, solve(arr[now], now+1, color));
        }else{
            ret = min(ret, solve(arr[now], now+1, color) + 1);
            if(arr[now] != color){
                int next;
                for(int i=now;i<=n;i++){
                    if(arr[i] != arr[i+1]){
                        next = i+1;
                        break;
                    }
                }
                ret = min(ret, solve(prev, next, color) + 1);
            }
        }
    }

    return ret;
}

int main()
{
    memset(dp, -1, sizeof dp);
    scanf("%d %d",&n, &k);
    for(int i=1;i<=n;i++) scanf("%d", &arr[i]);
    int ans = MAX;
    for(int i=1;i<=k;i++){
        ans = min(ans, solve(-1,1,i));
    }
    printf("%d\n", ans);

    return 0;
}

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

문제

문제

출처

ICPC

전구 문제 질문드려요

tols91 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말