[백준알고리즘] 16953번: A → B -C++

[백준알고리즘] 16953번: A → B -C++

16953번: A → B (acmicpc.net)

16953번: A → B

그리디 느낌이 나는 쉬운 문제를 찾다가 발견했다. 어려운 문제는 아니었으나, 문제 풀이를 생각했을 때 직관적으로 그리디 하게 풀 수 있겠다고 느꼈다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

정수 A에서 B로 바꿔야 한다. 아래의 두 가지 경우를 하나씩 사용해 최종적으로 B로 바꿔야 한다.

1. 2를 곱한다.
2. 가장 오른쪽 수에 1을 추가한다. (자리수 이동)

 

즉, 예제와 같이 A와 B가 각각 2와 162라면, 아래와 같이 변경할 수 있다. 최종적으로 4개의 연산이 요구된다. 하지만, 문제에서는 최소 연산에 1을 더한 값을 출력하라고 했기 때문에 5가 출력된다.

• 2 → 4 → 8 → 81 → 162

 

이를 해결하기 위해 역으로 생각했다. B에서 A로 만드는 것이다. 그럴 경우, 사용할 수 있는 연산도 다음 두 가지로 변경된다.

1. 2를 나눈다. (짝수여야 한다.)
2. 가장 오른쪽 수에 1을 제거한다. (자리수 이동) (1의 자릿수가 1이어야 한다.)

 

위의 조건을 봤을 때 짝수일 때는 1번 연산을 수행하고, 1의 자릿수가 1이라면 2번 연산을 수행하면 될 것이라는 것을 알 수 있다. 각 단계에서 위 두 조건을 모두 만족하지 못한다면, B에서 A로 만들 수 없는 것이다. 즉, A에서 B로도 만들 수 없다.

 

위의 조건들을 이용해 해결한 코드다.

#include <cstdio>

int main(void) {
	/* 입력 */
	int A, B;
	scanf("%d %d", &A, &B);

	/* 연산 횟수 */
	int iCnt = 0;
	while ( A < B ) {
		// 가장 오른쪽 1을 제거할 수 있음
		if ( 1 == B % 10 ) {
			B /= 10;
			iCnt++;
		}
		// 2로 나눌 수 있음
		else if ( 0 == B % 2 ) {
			B /= 2;
			iCnt++;
		}
		// 연산 불가능한 상황
		else {
			B = 0;
			break;
		}
	}

	/* 출력 */
	printf("%d", (A == B) ? iCnt + 1 : -1);

	return 0;
}