[14226] 이모티콘

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

<문제>

bfs로 푼다면 state를 {
cur : 현재 화면에 있는 이모티콘의 개수
clip : 현재 클립보드에 있는 이모티콘의 개수
turn : 현재까지 걸린 시간
}

처럼 구성해주면 된다.

dp로도 풀릴것 같았고, 실제로 solved.ac의 분류에도 다이나믹이 있었다.

 

처음에는 2차원을 생각했다. 아래처럼 구성하면 O(N^2)안에 풀릴것으로 생각했다.

dp[i][j] : i개의 이모티콘을 출력(cur), j개의 이모티콘을 저장(clip)한 상태의 최적해(turn)

 

여기서 시간이 아닌 공간을 조금 더 개선해볼 수 있다. dp를 1차원으로만 구성하는 것이다.

일반적인 dp는 이전에 구한 값을 재활용하므로, dp[i]를 구성할때엔 dp[0] ~ dp[i - 1]정도를 참조하나

"3. 화면에 있는 이모티콘 중 하나를 삭제한다" 의 연산을 구현하기 위해서

dp[i]를 구성할때에 dp[i+1]을 참조하게 된다.

dp[i] = dp[i + 1] + 1인 셈이다.

 

 

"1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다."

"2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다"

위 2개의 연산은 dp[i * j] = dp[i] + j의 점화식으로 표현할 수 있다.

3개의 이모티콘을 6개로 불릴때에는 2초가 소요된다.(저장 + 붙여넣기 1회)

9개로 불릴때에는 3초가 소요된다(저장+붙여넣기 2회)

이와 같은 방법으로, i의 배수꼴로 갱신해나가면 된다.

 

<소스코드>

#include<bits/stdc++.h>
using namespace std;
int s, dp[4001];
int main(void) {
    cin >> s;
    int i, j;
    for (i = 0; i <= 4000; i++)
        dp[i] = i;
    for (i = 1; i <= 1000; i++) {
        for (j = 2; ; j++) {
            if (i * j > 1000)break;
            dp[i * j] = min(dp[i] + j, dp[i * j]);
        }
        for (j = 1000; j >= 2; j--)
            dp[j] = min(dp[j + 1] + 1, dp[j]);
    }
    cout << dp[s];
    return 0;
}

dp의 갱신방법이 다소 독특하다, 재미있는 문제