[백준 14395] - 4연산(JAVA)

[문제] 

출처 -https://www.acmicpc.net/problem/14395

14395번: 4연산

---

[문제풀이] 

정수 s 가 있는데 이 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램 작성하라! 이다.

즉 한 정점 s 에서 정점 t 로 갈 수 있는 최소 연산 횟수 연산 횟수는 4가지 방법이 있는데 각 방법을 수행하면 연산 횟수 1이 증가한다. 여기서 문제를 그래프로 바꿀 수 있고 가중치가1인 최소의 횟수를 구하는거니까 BFS로 접근하여 문제를 해결 할 수 있다.

 

각 연산은 이렇게 나타 낼 수 있다.

 

1. s = s + s  --> s = 2*s

2. s = s - s  --> 0

3. s = s * s --> s²

4. s = s / s --> 1

 

문제에서 s의 범위가 10^9 라해서 만들어지는 연산의 최대 개수는 10^9이 아니다.

이 연산의 결과를 보면 결국 2번과 4번 연산은 0과 1을 만들기때문에, 1번과 3번 연산에 집중하면 된다.

s->s² 또는 2*s 형태이기 때문에 만들어지는 수는 s^a * 2^b 형태로 실제로는 10억개도 안되고 약 900개 정도가 나온다는 것을 알 수 있다.

 

즉, 10^9 의 크기만큼 배열을 만들어 방문처리 하지 않고 HashSet을 이용하여 방문처리를 하면 메모리를 아낄 수 있다.

---

[소스코드] 

import java.io.*;
import java.util.*;

public class Main {

	static class Node{
		long num;
		String cmd;
		Node(long num, String cmd){
			this.num = num;
			this.cmd = cmd;
		}
	}
	
	static final long limit = 1000000000L;
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		long s = Integer.parseInt(st.nextToken());
		long t = Integer.parseInt(st.nextToken());
		
		if(s == t) {
			System.out.println(0);
			return;
		}
		
		Queue<Node> q = new LinkedList<>();
		HashSet<Long> check = new HashSet<Long>();
		q.add(new Node(s,""));
		check.add(s);
		
		while(!q.isEmpty()) {
			Node p = q.poll();
			long num = p.num;
			String cmd = p.cmd;
			
			if(num == t) {
				System.out.println(cmd);
				return;
			}
			
			if(0<= num*num && num*num <= limit && !check.contains(num*num)) {
				q.add(new Node(num*num,cmd+"*"));
				check.add(num*num);
			}
			if(0<= num+num && num+num <= limit && !check.contains(num+num)) {
				q.add(new Node(num+num,cmd+"+"));
				check.add(num+num);
			}
			if(0<= num-num && num-num <= limit && !check.contains(num-num)) {
				q.add(new Node(num-num,cmd+"-"));
				check.add(num*num);
			}
			if(num != 0 && 0<= num/num && num/num <= limit && !check.contains(num/num)) {
				q.add(new Node(num/num,cmd+"/"));
				check.add(num/num);
			}
		}
		
		System.out.println(-1);
			
	}
		
}