백준 16157 (C++) 블로그

최초 업로드: 2025-09-01 16:43:10

최근 수정 시간: 2025-09-01 16:45:23

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] 블로그

[문제 링크](https://www.acmicpc.net/problem/16157)

## 문제 설명

neighbor 블로그를 운영하는 디디는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 스스로 해결한 경우 파란색, 도움을 받아 해결한 경우 초록색, 해결하지 못한 경우 빨간색으로 칠한다. 디디는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.

예를 들어, 각 문제를 위와 같은 색으로 칠할 때, 1번 문제를 초록색, 2번을 빨간색, 3~4번을 파란색, 5번을 초록색으로 순서대로 칠한다면 작업 횟수는 4번이지만, 1~5번 문제를 초록색, 2번을 빨간색, 3~4번을 파란색으로 순서대로 칠한다면 작업 횟수는 3번으로 가장 적다. 디디는 매일 100문제까지 시도하기 때문에, 이 작업이 꽤나 귀찮아지기 시작했다. 그래서 가장 효율적인 방법으로 위 작업을 수행하기를 원한다. 디디를 도와 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하는 프로그램을 작성하라.

## 입력

첫째 줄에 색을 칠해야 하는 문제의 수 N(1 ≤ N ≤ 100)이 주어진다.

둘째 줄에 N개의 문자가 공백없이 순서대로 주어진다. 각 문자는 i번째 문제를 어떤 색으로 칠해야 하는지를 의미하며, <code>R</code>은 빨간색, <code>G</code>는 초록색, <code>B</code>는 파란색을 나타낸다. 그 외에 다른 문자는 주어지지 않는다.

## 출력

첫째 줄에 디디가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라.

## 풀이
$BBBBBB$  
$......GGGGGG$  
이렇게 파란색 이후에 초록색을 그릴 때 일부가 겹쳐있는 경우

$BBBB$  
$.......GGGGGG$  
이렇게 겹치는 파란색 부분을 제외하고 그리는 것과 동일하다.

그래서 왼쪽 덩어리와 오른쪽 덩어리를 합치는 경우, 왼쪽 덩어리의 맨 왼쪽 색과 오른쪽 덩어리의 맨 오른쪽 색이 같은 경우에만 두 색을 한번에 칠할 수 있어 연산이 하나 줄어든다.

이를 3중 반복문과 2차원 dp로 해결할 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int dp[100][100]; // dp[L][R] : L ~ R 범위에 색을 채웠을 때의 최소 비용

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; string s; cin >> n >> s;

fill(&dp[0][0], &dp[99][100], INF);
 for(int i=0;i<n;i++) dp[i][i]=1;

for(int len=2;len<=n;len++) {
 for(int left=0;left+len-1<n;left++) {
 for(int beforeLen=1;beforeLen<len;beforeLen++) {
 dp[left][left+len-1] = min(dp[left][left+len-1], dp[left][left+beforeLen-1] + dp[left+beforeLen][left+len-1] - (s[left] == s[left+len-1]));
 }
 }
 }
 cout << dp[0][n-1];
}
```