Q_16953) A → B
4시간 꿈쩍않고 고민했던 문제
하지만 결과는 처참🥲
출처 : https://www.acmicpc.net/problem/16953
1st Try:
처음엔 백트래킹으로 풀어보려고 했다.
근데 어제 풀었던 순열 문제와는 너무나도 다르게
이 트리 자체가 어디까지 뻗어 나가는지 깊이를 제한할 수가 없었다.
때문에 list에 visit한 숫자들을 다 넣어주고 그 리스트에서 꺼낼 때 해당 list에서 아예 remove를 해주려고 했다.
숫자의 길이가 목표 숫자의 길이와 같을 때, 재귀함수를 멈춰주는 알고리즘;
은 처참히 실패🤦♀️
2nd Try:
bfs로 풀어보려고도 했다.
문제 내공이 덜 쌓여서 접근 방식을 모르겠더라.
내가 풀었던 bfs문제는 visited 배열을 사용했던 문제밖에 없었다.
그래서 난 당연히 써야하는줄 알았다.
Queue를 어떻게 써먹어야하지..?
count를 언제 늘려줘야하는 지 감도 잡히지 않았다.
처참히 실패🤦♀️
3rd Try:
도와주세요..
하고 다른 블로그 글들을 쓱쓱 넘겨봤다.
굳이 트리를 안 써도 되는 거였다.
즉, 거꾸로 연산을 해주면 되었던 것!
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
int count = 1;
long temp = b;
while (a < temp) {
String str = String.valueOf(temp);
if (temp % 2 == 0) {
temp /= 2;
count++;
} else if (str.substring(str.length() - 1, str.length()).equals("1")) {
temp = Long.parseLong(str.substring(0, str.length() - 1));
count++;
} else {
break;
}
}
if (a != temp) {
count = -1;
}
System.out.println(count);
}
}
1) 목표 숫자부터 역연산을 해주면서 2로 나눠서 나머지가 없을 경우 temp에 2로 나눈 값을 설정해준다.
2) 반대로 마지막 숫자가 1일 경우 (이 땐 당연히 2로 나누어 떨어지지 않기 때문에) 마지막 숫자를 제외한 후, long으로 바꾼다.
3) 만약 temp값이 목표 숫자보다 작아질 경우, 값을 비교해본다.
3-1) a와 temp가 같을 경우는 count를 리턴한다.
3-2) 다를 경우는 -1을 리턴한다.
..!
4th Try:
큐로 다들 활용은 어떻게 했는지 다른 벨로그를 참고했다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
int count = 0;
Deque<Long> deque = new ArrayDeque<>();
deque.add(a * 2);
deque.add(a * 10 + 1);
while (!deque.isEmpty()) {
count++;
int size = deque.size();
for (int i = 0; i < size; i++) {
Long p = deque.removeFirst();
if(p>b){
continue;
}
else if (p == b) {
System.out.println(count + 1);
return;
}
deque.add(p * 2);
deque.add(p * 10 + 1);
}
}
System.out.println(-1);
}
}
1) 일단 첫 2배를 해준 값과 기존 숫자에 1을 붙인 숫자를 deque에 삽입한다.
2) 후, deque 사이즈만큼 for loop을 돌면서 한 개씩 poll하면서 값 (p)을 비교한다.
*왜 사이즈만큼 loop을 도냐?!
해당 높이에 있는 모든 값들을 비교해줘야 함! (->dfs)
visited를 못 쓰는 대신 이 부분이 포인트인 것 같기도!
2-1) 만약 p가 b보다 크다면 절대 b는 될 수 없기 때문에 continue를 통해서 더 이상 비교하지 않는다.
2-2) p==b라면 count값을 출력한다.
2-3) 두 조건에 해당하지 않으면 p에 2배를 해준 값과 p에 1을 붙인 숫자를 deque에 삽입한다.
2-4) return;을 하지 않았는데 deque가 비어있는 경우, -1을 출력한다.
이해하는 데도 참 오래걸렸댜.
고민했는데 스스로 답을 찾지 못해서 조큼은 속상하다.
자료구조 관련해서 많은 연습이 필요할 것 같다.
