728x90
반응형
https://www.acmicpc.net/problem/14395
14395번: 4연산
첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.
www.acmicpc.net
|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
long long int s, t;
char gear[] = { '*','+','-','/' };
map<long long int, int>m;
struct Data {
long long int sum;
string a;
};
void init() {
cin >> s >> t;
}
void bfs() {
queue<Data>q;
Data c;
c.sum = s;
q.push(c);
while (!q.empty()) {
c = q.front(); q.pop();
if (c.sum == t) {
cout << c.a << endl;
return;
}
for (int dir = 0; dir < 4; dir++) {
if (dir == 0) {
Data n = c;
n.sum = n.sum * n.sum;
n.a.push_back(gear[dir]);
if (m[n.sum] == 0) {
m[n.sum] = 1;
q.push(n);
}
}
if (dir == 1) {
Data n = c;
n.sum = n.sum + n.sum;
n.a.push_back(gear[dir]);
if (m[n.sum] == 0) {
m[n.sum] = 1;
q.push(n);
}
}
if (dir == 2) {
Data n = c;
n.sum = n.sum - n.sum;
n.a.push_back(gear[dir]);
if (m[n.sum] == 0) {
m[n.sum] = 1;
q.push(n);
}
}
if (dir == 3) {
Data n = c;
if (n.sum == 0)continue;
n.sum = n.sum / n.sum;
n.a.push_back(gear[dir]);
if (m[n.sum] == 0) {
m[n.sum] = 1;
q.push(n);
};
}
}
}
cout << -1 << endl;
return ;
}
int main(void) {
init();
if (s == t) {
cout << 0 << endl;
return 0;
}
bfs();
return 0;
}
|
문제를 처음 접했을때 다짜고짜 dfs로 돌리려 했는데 그렇게 하면 탈출범위랑 몇개가 최소인지 명확하지 않는경우
엄청 깊이들어가 터질 수 있으니 bfs로 해야합니다.
그러면 훨씬 더 빠른 구현이 가능합니다.
포인트는 map stl을 이용해서 방문을 체크하고
string 변수를 가지고 다니면서 경로를 저장하고 원하는 값이 나온다면 저장한 경로를 출력하면 가장 빠른 경로가 됩니다.
그이유는 bfs의 특성 때문에 잘 넣어주면 찾을 수 있습니다.
그런 포인트를 빼고는 단순한 bfs와 동일하기에 다른 설명은 안하겠지만, 가장 중요한것은 자료형을 잘맞춰야 하는것
long long으로 될지 모르겠지만 10^9 인데 곱하고 더한다하면 절대 정수형 int로 안되기때문에 2^31 인가 그래서 -21 억 ~ 21억 가능해서 더 큰 정수형변수로 해야 정답이 됩니다. 꼭 주의하세요.
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 5213 과외맨 (0) | 2019.10.11 |
|---|---|
| 백준 3085 사탕게임 (0) | 2019.10.08 |
| 백준 9944 NxM 보드 완주하기 (0) | 2019.10.08 |
| 백준 2234 성곽 (0) | 2019.10.07 |
| 백준 2422 한윤정이 이탈리아에 가서 아이스크림을 (0) | 2019.10.07 |
댓글