백준 16953번

오늘 풀어본 문제는 백준의 16953번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

정수 $A$ 를 $B$ 로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

$2$ 를 곱한다.
$1$ 을 수의 가장 오른쪽에 추가한다.

$A$ 를 $B$ 로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 $A$, $B$ $(1 \leq A < B \leq 10^9)$가 주어진다.

출력

$A$ 를 $B$ 로 바꾸는데 필요한 연산의 최솟값에 $1$ 을 더한 값을 출력한다. 만들 수 없는 경우에는 $-1$ 을 출력한다.

풀이과정

1번째 시도

이 문제는 BFS를 이용하여 해결할 수 있는 문제이다. 각 숫자들을 정점으로 생각하고 std::queue 에 각 수와 변경된 횟수를 함께 저장하여 BFS를 진행하면 된다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int w[2] = { 2, 10 };
int b[2] = { 0, 1 };

vector<bool> visited;
queue<pair<int, int>> q;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int A, B, change = 0;
	cin >> A >> B;

	visited.resize(B + 1);
	visited[A] = true;
	q.push(make_pair(A, 0));

	while (!q.empty()) {
		int currentNumber = q.front().first;
		int currentStep = q.front().second;
		q.pop();

		for (int i = 0; i < 2; i++) {
			int newNumber = w[i] * currentNumber + b[i];

			if (newNumber == B) {
				cout << currentStep + 2;
				return 0;
			}
			else if (newNumber < B && visited[newNumber] == false) {
				visited[newNumber] = true;
				q.push(make_pair(newNumber, currentStep + 1));
			}
		}
	}

	cout << -1;

	return 0;
}

실행 결과 ‘런타임 에러 (IntegerOverflow)’ 가 발생하였다.

4번째 시도

런타임 에러의 설명이 나타내는 문제상황은 명확했다. 말 그대로 정수 오버플로우가 발생한 것이다. 변수들의 자료형을 바꾸어 해결할 수 있었고, 이 과정에서 몇 개의 변수에서 자료형을 바꾸는 것을 깜빡하여 추가적인 2번의 ‘틀렸습니다’가 발생하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

unsigned long long int w[2] = { 2, 10 };
unsigned long long int b[2] = { 0, 1 };

vector<bool> visited;
queue<pair<unsigned long long int, unsigned long long int>> q;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	unsigned long long int A, B, change = 0;
	cin >> A >> B;

	visited.resize(B + 1);
	visited[A] = true;
	q.push(make_pair(A, 0));

	while (!q.empty()) {
		unsigned long long int currentNumber = q.front().first;
		int currentStep = q.front().second;
		q.pop();

		for (int i = 0; i < 2; i++) {
			unsigned long long int newNumber = w[i] * currentNumber + b[i];

			if (newNumber == B) {
				cout << currentStep + 2;
				return 0;
			}
			else if (newNumber < B && visited[newNumber] == false) {
				visited[newNumber] = true;
				q.push(make_pair(newNumber, currentStep + 1));
			}
		}
	}

	cout << -1;

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

CLASS 4 문제이긴 해도 문제의 티어가 Silver라서 그런지 무난하게 풀 수 있는 문제였다. 일부로 실버로 고른 것은 아니고, 남은 CLASS 4 문제들 중 랜덤으로 선택한 문제니 일부로 쉬운 걸 골라서 푼다는 오해가 없길 바란다.

내일이면 9월이 되는 날이다. 잘 준비를 어느정도 마친 뒤 새벽에 8월을 되돌아보고 곧 다가올 개강에 어떻게 대비해야할지 생각해서 글을 하나 더 작성해보도록 하겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/16953

← Previous Post Next Post →