백준 24137 (C++) 塗り箸 (Chopsticks)

최초 업로드: 2025-09-02 12:30:00

최근 수정 시간: 2025-09-02 12:30:20

게시자: rlatjwls3333

카테고리: 백준

# [Platinum I] 塗り箸 (Chopsticks)

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

## 문제 설명

漆塗りお箸協会 (Japan Ohashi Institute) は，お箸の国際普及のためにデザインされたお箸 を用意することになった．お箸のうち，彩色される部分は一端から長さ Nmm にわたる部分で， 1mm ごとに色が定まっており，色が塗られない部分はない．また，お箸の彩色に使用する漆の 色は 52 色である．

漆塗り職人のあなたは，決められた色の通りに，お箸を塗る作業を依頼された．漆塗りには 手間がかかるため，なるべく少ない作業回数でお箸を完成させたい．

お箸を塗るための 1 作業とは，連続する区間を選び，その区間すべてを一色で塗ることであ る．この際，すでに色が塗られていた場所も必ず新しい色となる．お箸を完成させるために必 要な作業回数の最小値を求めるプログラムを書け．

## 입력

入力の 1 行目には 1 つの整数 N (1 ≤ N ≤ 300) が書かれて いる．これはお箸の彩色される部分の長さが Nmm であることを表す．

2 行目には，N 文字からなる英字 (A～Z, a～z) の列が与えられる．文字列の i 文字目が端から (i − 1)mm から imm までの色を表す．

## 출력

出力は，標準出力に行うこと．作業回数の最小値を表す 1 つの整数を出力せよ．

## 풀이
[백준 16157번](https://projectbpm.kro.kr/read/182), [백준 2449번](https://projectbpm.kro.kr/read/183)과 동일한 풀이로 해결 가능하다.

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

const int INF = 0x3f3f3f3f;

int dp[300][300];

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

fill(&dp[0][0], &dp[299][300], 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 leftLen=1;leftLen<len;leftLen++) {
 dp[left][left+len-1] = min(dp[left][left+len-1], dp[left][left+leftLen-1] + dp[left+leftLen][left+len-1] - (s[left] == s[left+len-1]));
 }
 }
 }
 cout << dp[0][n-1];
}
```