[BOJ] 백준 14226 이모티콘

문제 링크

www.acmicpc.net/problem/14226

14226번: 이모티콘

 

풀이

현재 클립보드에 들어있는 이모티콘의 개수와, 화면에 나타난 이모티콘의 개수를 바탕으로 상태를 정의합시다.

$d[clip][screen]$: 클립보드에 $clip$개, 화면에 $screen$개 이모티콘이 있을 때 시간의 최솟값입니다.

 

한 상태에서 갈 수 있는 다른 상태가 명확합니다.

1) $clip$을 $screen$으로 변경

2) $screen$을 하나 삭제

3) $screen$을 $clip$만큼 증가

 

기저 값은 이모티콘이 대충 $2n$개를 넘으면 최적이 안될 것 같아 $2n$을 기준으로 설정했습니다.

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;

int d[2222][2222];
int n;

// 1) clip 변경
// 2) 실제 개수를 하나 삭제
// 3) 실제 개수를 clip 만큼 증가
int go(int clip, int screen) {
    if (screen > 2 * n || clip > 2 * n) return INF;
    if (screen < 0) return INF;
    if (screen == n) return 0;

    int &ret = d[clip][screen];
    if (ret != -1) return ret;
    ret = INF;
    ret = min(ret, go(screen, screen) + 1);
    ret = min(ret, go(clip, screen - 1) + 1);
    ret = min(ret, go(clip, screen + clip) + 1);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(d, -1, sizeof(d));
    cin >> n;
    cout << go(0, 1);
}