[백준/C++] 14226번_이모티콘

문제는 다음과 같습니다.

bfs로 접근해서 풀었구요, stl queue를 이용했습니다.
queue의 자료형은 pair<pair<int, int>, int>를 이용해 '화면에 있는 이모티콘 수', '클립보드에 있는 이모티콘 수', '지금까지 걸린 시간' 이 3가지 변수를 담았습니다.

각각 s, c, t의 변수로 나타냈습니다.
그리고 스티커 개수의 중복을 확인하는 배열 ch를 선언해서 중복을 체크해주었습니다.

bfs가 수행되면서 실행되는 3가지 조건은 다음과 같습니다.

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

➡️이는 어떠한 조건도 요구하고 있지 않으며, 클립보드에 현재 화면에 있는 이모티콘의 개수만큼 추가된다.

    if(1){
      q.push({{s, s+c}, t+1});
    }

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

➡️클립보드만 비어있지 않아야하고, 화면에 있는 스티커의 개수가 나오지 않은 경우이어야 한다.(중복x)

    if(c!=0 && ch[s+c]==0){
      ch[s+c]=1; q.push({{s+c, 0}, t+1});
    }

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

➡️삭제한 개수가 >=0 이어야 하고, 그의 개수가 나오지 않은 경우이어야 한다.(중복x)

    if(s-1>=0 && ch[s-1]==0){
      ch[s-1]=1; q.push({{s-1, c}, t+1});
    }

전체 코드는 다음과 같습니다.

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

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

  int ch[100001]={0, };
  int n, s=1, t=0, c=0; queue<pair<pair<int, int>, int>> q; // s:화면, c:클립보드, t:시간
  cin>>n;
  ch[1]=1; q.push({{s, t}, c});

  while(!q.empty()){
    s = q.front().first.first; c = q.front().first.second; t = q.front().second; q.pop();
    if(s==n) break;

    if(1){
      q.push({{s, s+c}, t+1});
    }
    if(c!=0 && ch[s+c]==0){
      ch[s+c]=1; q.push({{s+c, 0}, t+1});
    }
    if(s-1>=0 && ch[s-1]==0){
      ch[s-1]=1; q.push({{s-1, c}, t+1});
    }
  }

  cout<<t<<endl;
  return 0;
}

---

아니 다시 점검해봤는데,
저 풀이가 왜 맞았는지 모르겠어요 ,, (시랑가)

다시 푼 풀이는 다음과 같습니다.

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

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

  int ch[10001][10001]={0, };
  int n, s=1, t=0, c=0; queue<pair<pair<int, int>, int>> q; // s:화면, c:클립보드, t:시간
  cin>>n;
  ch[1][0]=1; q.push({{s, t}, c});

  while(!q.empty()){
    s = q.front().first.first; c = q.front().first.second; t = q.front().second; q.pop();
    if(s==n) break;

    if(ch[s][s]==0){
      ch[s][s]=1;
      q.push({{s, s}, t+1});
    }
    if(c!=0 && ch[s+c][c]==0){
      ch[s+c][c]=1; q.push({{s+c, c}, t+1});
    }
    if(s-1>=0 && ch[s-1][c]==0){
      ch[s-1][c]=1; q.push({{s-1, c}, t+1});
    }
  }

  cout<<t<<endl;
  return 0;
}

생각해보니 첫번째와 두번째 조건이 틀린것 같았는데
저게 어떻게 맞았는지...
그리고 확인도 2차원 배열로 해야하는데
...😅

근데 첫번째 풀이는 0ms인 반면,
두번째 풀이는 216ms가 나왔다 ....
첫번째 풀이가 왜 맞았는지 저는 이해 못하겠는데,
아시면 댓글로 알려주세용 ㅜ,ㅜ

추가로 두번째 풀이를 개선한 풀이는 다음과 같습니다.
조건을 더 추가하여 공간복잡도와 시간복잡도를 최대한으로 줄여보았습니다.

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

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

  int ch[1001][1001]={0, };
  int n, s=1, t=0, c=0; queue<pair<pair<int, int>, int>> q; // s:화면, c:클립보드, t:시간
  cin>>n;
  ch[1][0]=1; q.push({{s, t}, c});

  while(!q.empty()){
    s = q.front().first.first; c = q.front().first.second; t = q.front().second; q.pop();
    if(s==n) break;

    if(ch[s][s]==0){
      ch[s][s]=1;
      q.push({{s, s}, t+1});
    }
    if(c!=0 && s+c<=n && ch[s+c][c]==0){
      ch[s+c][c]=1; q.push({{s+c, c}, t+1});
    }
    if(s-1>=0 && ch[s-1][c]==0){
      ch[s-1][c]=1; q.push({{s-1, c}, t+1});
    }
  }

  cout<<t<<endl;
  return 0;
}