글 읽기 - 아이디어 질문

sotter1020 5년 전 0

어떤 방식으로 짜야되나요?

제가 생각하면 인접하고 같은 수를 1 ~ k만큼 다 한번씩 돌려보는건데..

경우의 수가 너무 많아 비트마스크를 쓰고 다 써봐도

경우의 수를 다 담지 못해 오답이 나오고,

구글링하면서 나온 소스는 divide and conquer 방식으로

짠거 같은데 직관적으로 잘 와닿지 않아서요! 소스코드 첨부 드립니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 205
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
 
int n, m, arr[MAX], dp[MAX][MAX];
 
int fun(int s, int f)
{
  if (s == f)
    return 0;
  if (dp[s][f] != -1)
    return dp[s][f];
  // 이전에 s~f 범위 전구의 스위치 변환 횟수를 구했다면
  dp[s][f] = INF;
  for (int i = s; i < f; i++)
  {
    int tmp = arr[s] != arr[i + 1]? 1: 0;
    dp[s][f] = min(dp[s][f], fun(s, i) + fun(i + 1, f) + tmp);
    // s~f전구의 최소 변횐 횟수 = s~i, i+1~f 전구의 최소 변환 횟수 + tmp
  }
  return dp[s][f];
}
 
int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    scanf("%d", &arr[i]);
  memset(dp, -1, sizeof(dp));
  printf("%d",fun(1,n));
  return 0;
}

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

문제

문제

출처

ICPC

아이디어 질문

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말