반응형
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 |