M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 14226 - 이모티콘

최대 1 분 소요

문제

백준 14226 - 이모티콘 풀러가기

문제 분석

모든 연산은 1초 가 걸리고, 걸리는 시간의 최솟값 을 구해야 하는 문제다. 따라서 bfs를 이용하여 풀 수 있다.

문제 풀이

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    #include <cstdio>
    #include <queue>
    #include <cstring>
    #include <algorithm>
     
    using namespace std;
     
    int cnt[1001][1001];
     
    int main() {
        int s;
     
        scanf("%d", &s);
     
        memset(cnt, -1, sizeof(cnt));
        
        queue<pair<int,int>> q;
     
        cnt[1][0] = 0;
        q.push(make_pair(1, 0));
     
        int time = 1001;
     
        while (!q.empty()) {
            int screen = q.front().first;
            int clip = q.front().second;
     
            if (screen + clip < 1001 && cnt[screen+clip][clip] ==-1) {
                cnt[screen + clip][clip] = cnt[screen][clip] + 1;
     
                if (screen + clip == s) {
                    if (time > cnt[screen+clip][clip]) {
                        time = cnt[screen+clip][clip];
                    }
                }
     
                q.push(make_pair(screen + clip, clip));
            }
     
            if (cnt[screen][screen] == -1) {
                cnt[screen][screen] = cnt[screen][clip] + 1;
     
                q.push(make_pair(screen, screen));
            }
     
            if (screen - 1 >= 0 && cnt[screen - 1][clip] == -1) {
                cnt[screen - 1][clip] = cnt[screen][clip] + 1;
     
                if (screen - 1 == s) {
                    if (time > cnt[screen-1][clip]) {
                        time = cnt[screen-1][clip];
                    }
                }
     
                q.push(make_pair(screen-1, clip));
            }
     
            q.pop();
        }
     
        printf("%d", time);
     
        return 0;
    }
    		cs





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고