competitive-programming2021년 2월 27일1분 분량

[백준] 14226. 이모티콘 풀이

수정일: 2021년 2월 27일

Breadth first search

지원 언어:enko

#Problem

14226. 이모티콘

#Approach

전형적인 bfs 문제.

큐에 들어가는 element의 자료구조: $\{ \{ 현재 이모티콘 수, 클립보드의 이모티콘 수 \} , operation 횟수 \}$

$\{ \{ 1, 0 \} , 0 \}$ 에서 시작해서, 각 단계에서 아래의 탐색공간들을 추가로 탐색.

$s := 현재 이모티콘 수$
$clip := 클립보드의 이모티콘 수$
$o := operation 횟수$

$s = S$ 이면 $o$ 값을 출력, 종료
$s \gt 1$ 이고 $visited[s-1][clip] = false$ 이면 $\{\{ s-1, clip\} , o+1\}$ 를 탐색
$s + clip \le 1001$ 이고 $visited[s+clip][clip] = false$ 이면 $\{ \{ s+clip, clip \} , o+1 \}$ 를 탐색
$visited[s][s] = false$ 이면 $\{ \{ s, s \} , o+1 \}$ 를 탐색

#Code

/**
 * author: jooncco
 * written: 2021. 2. 27. Sat. 22:23:27 [UTC+9]
 **/

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <cmath>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef deque<int> di;
typedef deque<ii> dii;

const int LIMIT= 1001;

int S;
bool visited[1010][1010]= {0};

int main() {

    FAST_IO;
    cin >> S;

    queue<pair<ii,int>> Q;
    Q.push(make_pair({1,0},0));
    int ans= 0;
    while (!Q.empty()) {
        pair<ii,int> cur= Q.front(); Q.pop();
        int s= cur.first.first, clip= cur.first.second;
        int cnt= cur.second;

        if (s == S) {
            ans= cnt;
            break;
        }

        if ( s+clip <= LIMIT && !visited[s+clip][clip] ) visited[s+clip][clip]= 1, Q.push( make_pair({s+clip,clip}, cnt+1) );
        if ( !visited[s][s] ) visited[s][s]= 1, Q.push( make_pair({s,s}, cnt+1));
        if ( s > 1 && !visited[s-1][clip] ) visited[s-1][clip]= 1, Q.push( {make_pair(s-1,clip}, cnt+1) );
    }

    cout << ans;
}

#Complexity

Time: $O(S^2)$
Space: $O(S^2)$