[BOJ] 14226. 이모티콘

이모티콘

클릭시 이동합니다.

어떻게 풀까?

우선, 한 상태에서 달라질 수 있는 것들은 총 3개 이죠.

1. 현재 화면에 있는 이모티콘 수

2. 클립보드에 저장된 이모티콘의 수

3. 시간

특히, 시간 같은 경우는 모든 연산에서 1초로 동일합니다.

따라서, bfs를 이용해서 딱 현재 화면에 있는 이모티콘의 수가 처음으로 나온다면, 그것이 바로 해당 화면에 이모티콘을 만들 수 있는 최소의 시간인 것이죠.

그럼, 만약 큐에서 상태를 뽑았는데, 이미 이전에 화면에 있는 이모티콘의 수와 클립보드에 저장된 이모티콘의 수가 같은 상태를 봤었다면 어떨까요??

어짜피 똑같은 처리를 다시 한 뒤에 똑같은 상태가 큐에 저장되기 때문에 다시 볼 필요가 없습니다!!

따라서, 이전에 처리한 상태를 저장하기 위해서 

visit은 [화면에 있는 이모티콘][클립보드에 있는 이모티콘] 을 만듭시다.

만약, visit[화면에 있는 이모티콘][클립보드에 있는 이모티콘] 이 true라면, 해당 상태는 무시해도 된다는 것이죠!

그럼 이제 한 상태에서 다음 상태를 만드는 방법을 알아봅시다.

각 상태마다는 딱 3개의 연산을 할 수 있습니다!

1. 현재 이모티콘을 모두 복사해서 클립보드에 저장하기.

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

3. 화면에 있는 이모티콘 하나 삭제하기.

앗, bfs를 효율적으로 이용하기 위해서 만약 중복처리를 위해서 visit배열을 만들려고 했는데, 3번 때문에 약간 꼬일수가 있습니다.

화면에 있는 이모티콘을 몇 개까지 저장해야 하는지 애매해지기 때문입니다!

그렇다면, 일단 어떤경우에서든 만들 수 있는 방법을 한 번 생각해 봅시다. 

시작이 1개의 이모티콘과 0개의 클립보드로 시작합니다.

그렇다면, 1개의 이모티콘을 클립보드에 넣고 계속 붙여넣으면 원하는 개수의 이모티콘을 만들 수 있을 것입니다.

하나씩 이모티콘을 늘리는 것과 같은 방법이죠.

만약, 만들어야 하는 이모티콘의 개수가 1천개라면 1천초가 소요된다는 것이죠!

즉, 어떤 경우에서든지, 2000을 넘는 이모티콘의 개수는 필요 없다는 것입니다!

2000개를 넘으면 1개씩 지우는 경우에서는 항상 1000초를 넘기기 때문이죠!

이미 어떤 수에서든지 1천 초 내에 해결할 수 있다는 것을 알았는데, 1천 초를 넘기는 상태를 저장할 필요는 없습니다.

그렇다면, 이제 한 상태에서 다음 상태를 만드는 방법은 다음과 같이 정리할 수 있습니다.

1번 연산 상태를 저장할 때에는, 클립보드에 이모티콘의 개수가 2천개가 넘지 않을 때에만 다음 상태를 만들어서 큐에 넣고,

2번 연산 상태를 저장할 때에는 화면의 이모티콘의 수가 2천개가 넘지 않을 때에만 다음 상태를 만들어서 큐에 넣으면 됩니다.

3번 연산의 경우에는 화면에 있는 이모티콘이 0개가 안될 때에만 다음 상태를 만들어서 큐에 넣으면 되겠죠!

그리고 큐에서 뽑을때마다 화면에 있는 이모티콘의 개수가 S개가 되는지 확인하고, 된다면 해당 시간을 리턴해주면 됩니다!

코드

//https://www.acmicpc.net/problem/14226
//이모티콘
#pragma once
#include<cstdio>
 
int que[1000000][3], f, r;
bool visit[2001][2001];
 
int main() {
    int s, clip = 0;
    scanf("%d\n", &s);
 
    visit[1][0] = true;
    que[r][0] = 1;
    que[r][2] = 0;
    que[r++][1] = 0;
 
    int cnt = 0, t = 0;
    while (f != r) {
        int now[3] = { que[f][0], que[f][1], que[f++][2] };
        
        if (now[1] && now[0]+ now[1] == s) {
            t = now[2] + 1;
            break;
        }
        else if (now[1] && now[0] + now[1] < 2001) {
            if (!visit[now[0] + now[1]][now[1]]) {
                visit[now[0] + now[1]][now[1]] = true; 
                que[r][0] = now[0] + now[1];
                que[r][1] = now[1];
                que[r++][2] = now[2] + 1;
            }
        }
 
        if (now[0] > 0) {
            if (!visit[now[0] - 1][now[1]]) {
                visit[now[0] - 1][now[1]] = true;
 
                que[r][0] = now[0] - 1;
                que[r][1] = now[1];
                que[r++][2] = now[2] + 1;
            }
        }
 
        if (visit[now[0]][now[0]]) continue;
        visit[now[0]][now[0]] = true;
 
        que[r][0] = que[r][1] = now[0];
        que[r++][2] = now[2] + 1;
    }
    printf("%d\n", t);
    return 0;
}

여담

최악의 경우는 visit이 모두 가득차는 경우일 것입니다. 이는 이 되죠!