취미로 코딩하기

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

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

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

주어진 유리수를 7진법으로 나타냈을 때의 소수점 아래 특정 자릿수를 구하는 문제이다.

10진수의 나눗셈 과정을 다시 생각해보자. 남은 분자에 10을 곱하고 분모로 분자를 나눈 몫을 자릿수로 나타낸 다음 분자의 값을 분모로 나눈 나머지로 바꾸는 것을 반복하는 것으로 문제를 해결할 수 있을 것이다.

7진수의 나눗셈 또한 위의 과정과 크게 다르지 않다. 다른 점은 분자에 곱하는 값이 10이 아닌 7이 되는 것 하나뿐이다. 이를 구현해 문제를 해결하자.

입력으로 주어지는 유리수는 가분수일 수 있으므로 첫 자리를 구하기 전에 분자를 분모로 나눈 나머지로 바꿔야 함에 유의하자.

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

#include <iostream>
using namespace std;

int T;
int A, B, L, R;

void solve() {
	A %= B;
	for (int i = 0; i <= R; i++) {
		A *= 7;
		int dgt = A / B; A %= B;
		if (L <= i) cout << dgt;
	}
	cout << '\n';
}

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> A >> B >> L >> R;
		cout << "Problem set " << t << ": " << A << " / " << B << ", base 7 digits " << L << " through " << R << ": ";
		solve();
	}
}