[C++][백준 14226번][백준 이모티콘][bfs][dp]

문제

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

풀이방법

BFS로 풀면 된다.

이때 이 문제에서 다른 문제와 달리 두가지를 확실히 짚고 넘어가겠다.

1.많은 분기를 막기 위해 2차원 배열 하나를 만들어 주어 array[화면의 이모티콘 수][저장된 클립보드의 수] 가 겹치는 경우 더 이상 분기하지 않도록 한다.
(array[화면의 이모티콘 수][저장된 클립보드의 수] 가 1인 경우는 이미 이전 시간대에 지나갔음을 의미)

2.화면에 이모티콘이 2000개 이상 있는경우는 없다. 그 이유는 이모티콘은 1000개 이하를 요구한다. 
따라서 화면에 이모티콘을 2000개가 있어버리면, 1000개 이하의 수를 만들기 위해 <3번조건-화면에 있는 이모티콘 중 하나를 삭제>만 사용 가능함에 따라 1000초 이상이 걸린다. 
하지만 시작하자마자 화면에 있는 1개를 복사하여 붙여넣기 하면 1000초안에 1000개의 수를 모두 만들 수 있게 된다.

그리고 queue로 push해주는 경우는 다음과같이 세가지로 나누었다.

1.화면에 있는 이모티콘을 복사

2.클립보드에 있는 이모티콘을 복붙

3.화면의 이모티콘 중 하나를 삭제

분기를 나누어 주는 순서는 상관 없지만 나는 2-1-3 순서로 하였다.

2번의 조건은 다음과 같다.

if(화면에 있는 모든 이모티콘 + 클립보드의 이모티콘 < 2000 
&&
array[화면의 이모티콘 수][저장된 클립보드의 수] ==0)

1번의 조건은 다음과 같다.

if((화면에 있는 이모티콘 <1000)
&&
array[화면의 이모티콘 수][저장된 클립보드의 수] ==0)
여기서 화면에 있는 이모티콘<1000의 경우는, 화면에 이모티콘이 1000개가 있으면 이것을 복사하여 붙여 넣게 되면 2000이 넘기 때문에 이러한 조건을 걸어주었다.

3번의 조건은 다음과 같다.
if((화면에 있는 이모티콘>1)
&&
array[화면의 이모티콘 수][저장된 클립보드의 수] ==0)
화면에 있는 이모티콘이 1개이면 이상태에서 삭제해버리면 0개가 되기 때문이다.

코드

#include <queue>
#include <utility>
#include <iostream>
using namespace std;
int main()
{
    bool **ck; //check
    ck = new bool *[2001];
    for (int i = 0; i < 2001; i++)ck[i] = new bool[2001]();
    ck[1][0] = 1;
    queue<pair<int,int>> q;
    q.push(make_pair(1, 0));
    int cb = 0; //clipboard
    int dp = 1; //display 
    int input;
    cin >> input;
    int time = 0;
    int popnum=0;
    while (!q.empty()) {
            popnum = q.size();
            while (popnum--) {
                dp = q.front().first;
                cb = q.front().second;
                if (dp == input) {
                    cout << time;
                    exit(0);
                }
                q.pop();
                //1.붙여넣기
                if (dp + cb < 2000 && !ck[dp + cb][cb]) {
                    q.push(make_pair(dp + cb, cb));
                    ck[dp + cb][cb] = 1;
                }
                //2.복사하기
                if (dp < 1000 && !ck[dp][dp]) { //dp가 1000이 되면 cb가 1000이 되어 복붙시 2000이 된다.
                    q.push(make_pair(dp, dp));
                    ck[dp][dp] = 1;
                }
                //3.이모티콘 삭제하기
                if (dp > 1 && !ck[dp - 1][cb]) {
                    q.push(make_pair(dp - 1, cb));
                    ck[dp - 1][cb] = 1;
                }
            }
            time++;
        }
    return 0;
}

추가 고찰[dp]

이 문제를 풀고나니 다음과 같이 dp로 풀 수 있을것 같다는 생각을 하였다.

  dp[화면의 이모티콘 수][클립보드]+1=
  dp[화면의 이모티콘 수+클립보드][클립보드]

  dp[화면의 이모티콘 수][클립보드]+1= 
  dp[화면의 이모티콘 수-1][클립보드]

  dp[화면의 이모티콘 수][클립보드]+1=
  dp[화면의 이모티콘 수][화면의 이모티콘 수]

이런식으로 하면 더 빠른 속도로 풀 수 있을 것이다.