반응형

https://www.acmicpc.net/problem/16397

 

16397번: 탈출

첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어서 해당 숫자가 만들어진 적이 있는지 체크합니다.

 

2. bfs를 이용하여 버튼을 누를 때마다 queue에 숫자와 버튼을 누른 횟수를 push 합니다.

 

3. 현재 숫자가 G와 일치하면 cnt를 출력하고, queue가 빌 때까지 G와 같지 않다면 ANG를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, T, G;
int visited[100001];
 
int buttonB(int num)
{
    num *= 2;
 
    int temp = 100000;
 
    while (num < temp) temp /= 10;
 
    num -= temp;
 
    return num;
}
 
int main()
{
    scanf("%d %d %d", &N, &T, &G);
 
    queue<pair<int, int>>q;
 
    q.push({ N,0 });
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (visited[cur] == 1 || cur > 99999 || cnt > T) continue;
        visited[cur] = 1;
 
        if (cur == G) {
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[cur + 1] != 1) {
            q.push({ cur + 1,cnt + 1 });
        }
 
        if (cur < 50000) {
            const int B = buttonB(cur);
 
            if (visited[B]!=1) {
                q.push({ B,cnt + 1 });
            }
        }
    }
 
    printf("ANG");
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 12014번 - 주식 (C++)  (0) 2022.12.17
[ 백준 ] 1365번 - 꼬인 전깃줄 (C++)  (0) 2022.12.16
[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12

+ Recent posts

티스토리툴바