알고리즘 풀이/백준(Boj)
백준(BOJ) 4연산
100win10
2019. 10. 16. 02:04
문제 : https://www.acmicpc.net/problem/14395
14395번: 4연산
첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.
www.acmicpc.net
풀이 :
t가 10억이지만 n은 2*n 의 형태나 n^2 의 형태이기 때문에 탐색하는 n의 수는 많지 않고 BFS로 접근할 수 있다.
queue<pair<long long, string>> q를 생성한후에 * + - / 각각의 순서대로 결과값과 그때의 붙는 부등호의 값을
큐에 넣는다.
조건은 10억이하일 경우 q에 넣어야 하고 나눌때에 n은 0이여서는 안된다. 또 같은 값을 다시 넣지 않기 위해
stl set을 통하여 중복을 막아주자.
코드 ( C++ )
