[백준]#14395 4연산
문제
정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.
사용할 수 있는 연산은 아래와 같다.
- s = s + s; (출력: +)
- s = s - s; (출력: -)
- s = s s; (출력: )
- s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)
입력
첫째 줄에 s와 t가 주어진다.
출력
첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.
연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.
예제 입력 1
7 392
예제 출력 1
+*+
예제 입력 2
7 256
예제 출력 2
/+***
예제 입력 3
4 256
예제 출력 3
**
예제 입력 4
7 7
예제 출력 4
0
예제 입력 5
7 9
예제 출력 5
-1
예제 입력 5
10 1
예제 출력 5
/
풀이
이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 쉽게 풀 수 있었다. 최대값이 이기 때문에 중복 체크를 HashSet을 이용했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int target = Integer.parseInt(input[1]);
if(start==target) { //타겟 값과 같은 경우
System.out.println(0);
return;
}
bfs(start, target);
}
public static void bfs(int start, long target) {
Queue<Pair> queue = new LinkedList<>();
HashSet<Integer> set = new HashSet<>();
int min_len = Integer.MAX_VALUE;
String ans = "";
set.add(start);
queue.add(new Pair(start, ""));
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(temp.num==target) { //타겟 값에 도달한 경우 최소값 유효성 체크
if(min_len>=temp.str.length()) {
if(min_len==temp.str.length()) {
ans = ans.compareTo(temp.str) < 0 ? ans : temp.str;
}
else {
min_len = temp.str.length();
ans = temp.str;
}
}
}
if(!set.contains(0)) { //'-'는 무조건 0 이기 때문에 처음에 먼저 계산
set.add(0);
queue.add(new Pair(0, "-"));
}
if(!set.contains(1)) { //'/'는 무조건 1 이기 때문에 마찬가지로 먼저 계산
set.add(1);
queue.add(new Pair(1, "/"));
}
if((long)temp.num*temp.num<=target && !set.contains(temp.num*temp.num)) { //'*'가 가능한 경우, '*'가 '+'보다 아스키 코드 값이 작기 때문에 먼저 체크
if(temp.num*temp.num==target)
queue.add(new Pair(temp.num*temp.num, temp.str+"*"));
else {
set.add(temp.num*temp.num);
queue.add(new Pair(temp.num*temp.num, temp.str+"*"));
}
}
if((long)temp.num+temp.num<=target && !set.contains(temp.num+temp.num)) { //'+'가 가능한 경우
if(temp.num+temp.num==target)
queue.add(new Pair(temp.num+temp.num, temp.str+"+"));
else {
set.add(temp.num+temp.num);
queue.add(new Pair(temp.num+temp.num, temp.str+"+"));
}
}
}
if(ans.equals("")) //도달 불가능한 경우
System.out.println(-1);
else
System.out.println(ans);
}
public static class Pair {
int num;
String str;
public Pair(int num, String str) {
this.num = num;
this.str = str;
}
}
}
Author And Source
이 문제에 관하여([백준]#14395 4연산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준14395-4연산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)