취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 32791번 문제인 Exact Change이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/32791

먼저 두 수 중 더 작은 수의 앞에 leading zero를 추가해 자릿수를 같게 해두자.

이제, 가장 앞자리부터 살피면서 서로 다른 자릿수가 나올 때까지는 해당 자리의 수가 1일 경우 그에 대응되는 액면가의 화폐를 집합에 포함하고, 그렇지 않다면 다음 자리로 넘어가자. 해당 자리가 둘 다 0이면 아무 문제 없고, 1이면 모든 액수를 구성하는 데에 그 자리에 해당하는 액면가의 화폐가 필요할 것이며 나머지 자리들은 해당 자리를 지워 얻은 두 수 사이의 수를 표현할 수 있으면 되기 때문이다.

처음으로 다른 값이 나온 자리가 있을 경우, 해당 자리가 1인 수가 존재할 수밖에 없으며 그 자리가 0이고 이후의 자리가 모두 1인 수 또한 항상 표현이 가능해야 하므로 해당 자리를 포함한 모든 자리에 대응되는 액면가의 화폐가 필요함을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <utility>
using namespace std;

int N, ans;
string A, B, s;

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

	cin >> B >> A;
	while (A.length() > B.length() + s.length()) s += '0';
	s += B;
	swap(B, s);
	N = A.length();
	for (int i = 0; i < N; i++) {
		if (A[i] != B[i]) {
			ans += N - i;
			break;
		}
		else if (A[i] == '1') ans++;
	}
	cout << ans;
}