취미로 코딩하기

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

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

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

복권의 각 라운드의 상금이 계속 2배씩 증가하므로, 가장 많은 상금을 타가는 사람은 결과적으로 복권의 마지막 라운드의 당첨자가 된다.

마지막 라운드에서 발행된 전체 티켓수와 각 참가자들이 마지막 라운드에서 구입한 티켓 수를 이용해 답을 구하자.

답을 기약분수의 형태로 출력해야한다는 점에 유의하자. 이는 유클리드 알고리즘(Euclidean algorithm)을 이용해 최대공약수(gcd)를 구해내는 것으로 쉽게 구현할 수 있다.

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

#include <iostream>
using namespace std;

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

int arr[10001];

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

	int N, R; cin >> N >> R;
	while (N) {
		int total = 0;
		for (int n = 0; n < N; n++) {
			auto& x = arr[n];
			for (int r = 0; r < R; r++) cin >> x;
			total += x;
		}
		for (int n = 0; n < N; n++) {
			int GCD = gcd(arr[n], total);
			cout << arr[n] / GCD << " / " << total / GCD << '\n';
		}

		cin >> N >> R;
	}
}