반응형

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

 

14395번: 4연산

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.  연산의 아

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map을 활용하여 s의 방문 여부를 체크합니다.

 

2. bfs를 돌면서 우선순위를 '*', '+', '-', '/' 순으로 queue에 push 합니다.

 

3. s와 t가 같아지면 지금까지 수행된 연산을 출력합니다.

 

4. s가 t와 같아질 수 없다면 -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<iostream>
#include<queue>
#include<string>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
int main()
{
    ll s, t;
    unordered_map<ll, int> m;
 
    scanf("%lld %lld", &s, &t);
 
    if (s == t) {
        printf("0");
        return 0;
    }
 
    queue<pair<ll, string>> q;
 
    string str;
 
    q.push({ s,str });
 
    while (!q.empty()) {
        const ll cur = q.front().first;
        const string str = q.front().second;
        q.pop();
 
        if (m[cur] != 0) continue;
        m[cur] = 1;
 
        if (cur == t) {
            cout << str;
            return 0;
        }
 
        if (cur * cur <= t) {
            if (m[cur * cur] != 1) {
                q.push({ cur * cur,str + '*' });
            }
        }
 
        if (cur * 2 <= t) {
            if (m[cur * 2] != 1) {
                q.push({ cur * 2,str + '+' });
            }
        }
 
        if (m[0] != 1) {
            q.push({ 0, str + '-' });
        }
 
        if (cur != 0) {
            if (m[1] != 1) {
                q.push({ 1,str + '/' });
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 19538번 - 루머 (C++)  (0) 2022.12.24
[ 백준 ] 1922번 - 네트워크 연결 (C++)  (0) 2022.12.23
[ 백준 ] 12738번 - 가장 긴 증가하는 부분 수열 3 (C++)  (0) 2022.12.21
[ 백준 ] 1818번 - 책정리 (C++)  (0) 2022.12.20
[ 백준 ] 22255번 - 호석사우루스 (C++)  (0) 2022.12.19

+ Recent posts

티스토리툴바