[BOJ 27505 // C++] 천국의 계단

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

 

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

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

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;
}