취미로 코딩하기

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

이번에 볼 문제는 백준 27505번 문제인 천국의 계단이다.
문제는 아래 링크를 확인하자.

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

높이가 \(A\)인 직육면체와 \(B\)인 직육면체로 만들 수 있는 모든 높이의 가짓수를 구할 수 있다면 \(N\)에서 해당 가짓수를 빼는 것으로 문제를 해결할 수 있다. 만들 수 있는 모든 높이의 가짓수를 구해보자.

먼저 \(A\)와 \(B\)가 서로소라고 가정해 보자. 어떤 높이가 \(H\)인 어떤 단이 높이가 \(B\)인 직육면체를 \(A\)개 이상 사용해 만들어진다면 높이 \(H\)인 단은 높이 \(B\)인 직육면체 \(A\)개를 높이 \(A\)인 직육면체 \(B\)개로 바꿔서 만들 수도 있음을 관찰하자. 즉, 어떤 높이 \(H\)인 단이 만들어질 수 있다면 높이 \(B\)의 직육면체를 \(A\)개 미만으로 사용해 항상 만들 수 있음을 알 수 있다. 주어지는 \(A\)와 \(B\)의 크기가 충분히 작으므로(1천만 이하), 높이가 \(B\)인 직육면체를 0개, 1개, ..., \(A-1\)개 사용해 만들 수 있는 단의 높이의 개수를 각각 구해 더하는 것으로 필요한 값을 구할 수 있다.

\(A\)와 \(B\)가 서로소가 아니라면 어떨까? 이 경우 \(B\)의 배수가 가장 빠르게 \(A\)의 배수가 되는 경우는 \(B\)에 \(A/\gcd (A,B)\)를 곱했을 때가 됨은 쉽게 관찰할 수 있다. 이를 활용해 이 경우 또한 \(A\)와 \(B\)가 서로소인 경우와 같은 방법으로 문제를 해결할 수 있다.

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

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y) return gcd(y, x % y);
	return x;
}

ll N, A, B, AA, G;
ll cnt;

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

	cin >> N >> A >> B;
	G = gcd(A, B);
	AA = A / G;
	for (ll b = 0; b < AA; b++) {
		ll K = N - B * b;
		if (K < 0) break;
		cnt += K / A + 1;
	}

	cout << N - cnt + 1;
}