문제 내용
https://www.acmicpc.net/problem/16953
16953번: A → B
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
www.acmicpc.net
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
문제 접근 방법
그리디 알고리즘이란 간단히 말하면 D라는 정답까지 도출하기 위해 A, B, C 라는 최적의 답을 하나씩 구해 나가는 과정이다. 즉, 지역적으로 최적인 해는 전역적으로 최적인 해가 되는것이다.
그리디 알고리즘에서 로직을 구성할때 3가지를 고려해야한다.
- 선택
현재 상태에서 가장 최적의 조건 선택 - 적절성 검사
1번에서 선택한 조건이 현재 최적의 해를 구할때 적절한지 검사 - 해답 검사
2번까지 과정을 거치고 나온해가 내가 구하고자 하는 답인지 검사
아니라면 다시 1~2번 과정 반복
그리디는 위의 3가지를 고려하며 로직을 짠다.
이 문제에서 예를 들어보자.
- 선택
주어진 입력값에대해 2를 곱할지, 1을 추가할지 선택 - 적절성
선택에 의해 도출될 값이 적절한 값인지 검사
즉, 입력값이 2일때 4 or 21이 나와야함. 만약 22같은 숫자가 나오면 적절하지 않은것. - 해답
초기값이 2 , 최종적으로 도달하고자 하는값이 2004 일때
첫번째 실행후 21 or 4 가 2004인지 검사하고 아니라면 1~2번 다시 반복.
문제에서 예를 들면 위와같은 과정을 거치게된다.
그리고 이문제는 초기값 a에서 최종값 b로 만들수도 있지만
나는 최종값 b를 초기값 a로 만들도록 로직을 짰다.
이렇게 로직을 짠이유는 a를 b로 만들 경우 1을 붙일경우와 2를 곱할경우를 나눠서 최적해를 생각해야 하지만
b를 a로 만들경우 짝수면 무조건 나누고 홀수면 무조건 마지막 숫자 없애기만하면 지역적인 최적해가 나오기 때문이다.
풀이내용은 아래와 같다.
풀이내용
- 선택
b를 2로 나눌지 가장 오른쪽의 수를 버릴지 선택 - 적절성
b를 2로 나누거나 가장 오른쪽 한자리수를 버렸을때 적절한 값이 나왔는지 검사
이때 2로 나눠지거나 가장 오른쪽 한자리수가 1이 였다면 횟수 증가.
만약 2로 안나눠지고 가장 오른쪽 한자리수가 1이 아니라면 -1을 반환. - 해답
1~2번 과정으로 최종값을 초기값으로 만들었다면 '지금까지 횟수+1'을 해서 출력.
해답이 안나왔다면 1~2번 반복.
1~2번 반복하는 도중 값이 초기값 a 보다 작아진다면 b는 a로 바꿀수 없는 수 이므로 -1 반환.
본인은 위의 과정으로 문제를 풀었다.
자세한 내용은 코드를 보자
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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 ori = Long.parseLong(st.nextToken());//초기값
long target = Long.parseLong(st.nextToken());//최종값
System.out.println(changeNum(ori, target));
}
public static int changeNum(long ori, long target) {
int cnt=1;//반환값, 반환값은 최소횟수+1 이므로 초기값 1로 설정.
while(true) {
if(ori==target) break;//최종값이 초기값과 같아지면 중단.
else if(ori>target) {//최종값이 초기값으로 될수 없다면 cnt 갱신 후 중단.
cnt = -1;
break;
}
if(target%2==0) {//2로 나눠진다면 2로 나누기
target = target/2;
cnt++;
}else if(target%10==1) {//끝자리가 1이라면 1제외 시키기
target = target/10;
cnt++;
}else {//끝자리가 홀수인데 1이 아니라면 cnt 갱신 후 중단.
cnt=-1;
break;
}
}
return cnt;
}
}마치며
어렵지 않은 문제이다.
다만 마지막 자리수가 1인지 아닌지에 대한 분기문만 잘 작성하면 무리없이 맞출수 있는 문제라고 생각한다.