백준 17504 - 제리와 톰(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17504

17504번: 제리와 톰 2

사칙 연산 문제였습니다.

문제를 풀기 위해서 구현해야 할 것이 있습니다.

1. 분자와 분모 바꾸기

2. 분수와 정수 더하기

3. 최대 공약수를 찾은후 기약분수로 만들기

     -> 더해야 할 값들이 커짐으로 기약분수로 만들어주는 것이 필수였습니다.

 

 

최대 공약수를 구하는 코드입니다.(유클리드 호제법입니다.)

long long Uclid(long long x, long long y){
	long long X = x;
	long long Y = y;
	while(1){
		if(Y == 0) return X;
		long long tmp = X % Y;
		X = Y;
		Y = tmp;
	}
}

 

정수와 분수를 더하는 부분은 어렵지 않았습니다.

예를 들어, 7 + 4/5를 했을 때, 분자는 7 * 5 + 4가 되고 분모를 5로 같습니다.

정수에 분모를 곱해준 값을 분자에 넣어주면 됩니다.

 

값이 커질 수 있기에 더해줄 때마다 최대 공약수를 구해서 약분 해주셔야합니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

#define P pair<long long, long long>
#define PP pair<P, int>
#define F first
#define S second

using namespace std;

int N;
vector<int> number;
P ans = {1, 1}; // 분자 분모 순서

long long Uclid(long long x, long long y){
	long long X = x;
	long long Y = y;
	while(1){
		if(Y == 0) return X;
		long long tmp = X % Y;
		X = Y;
		Y = tmp;
	}
}

P Add(int x, P y){
	if(x >= 1) y.F = y.F + (x * y.S);
	else y.F = (-x * y.S) - y.F;
	long long div = Uclid(y.F, y.S);
	y.F /= div;
	y.S /= div;
	return y;
}

P Reverse(P x){
	P tmp = {x.S, x.F};
	x = tmp;
	return x;
}

void solve() {
	ans.S = number[N-1];
	for(int i = N-2; i >= 0; i--){
		ans = Add(number[i], ans);
		ans = Reverse(ans);
	}
	ans = Add(-1, ans);
	cout << ans.F << " " << ans.S;
}
	 

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		int x;
		cin >> x;
		number.push_back(x);
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요