[BOJ 10291 // C++] Ribbon

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

 

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

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

 

먼저 주어지는 리본의 길이를 사용하지 못하는 부분을 미리 제거한 길이로 전처리해두자.

 

남은 사용할 수 있는 부분의 리본은 모두 이용되어야 하고 모두 길이가 같게 잘려야 하므로, 모든 전처리된 리본의 길이는 잘린 리본의 길이의 배수여야 할 것이다. 따라서 잘린 리본의 길이는 모든 전처리된 리본의 길이의 공약수가 되어야 함을 알 수 있다.

 

가능한 가장 긴 리본의 길이를 구해야 하므로 주어진 수들의 최대공약수를 구해 문제를 해결하자. 이는 유클리드 호제법(Euclidean Algorithm)을 이용해 구할 수 있다.

 

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

#include <iostream>
using namespace std;

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

int N;
int A[10];
int G;

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

	while (cin >> N) {
		G = 0;
		for (int i = 0; i < N; i++) {
			cin >> A[i];
			A[i] -= 2;
			G = gcd(G, A[i]);
		}
		
		for (int i = 0; i < N; i++) G = gcd(G, A[i]);
		int ans = 0;
		for (int i = 0; i < N; i++) ans += A[i] / G;
		cout << G << ' ' << ans << '\n';
	}
}