백준 10166번: 관중석 문제풀이코드 C++

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

10166번: 관중석

 

접근방법[알고리즘]

 

2차원 배열로 분수 형태를 나타낼 수 있다.

분수를 기약분수로 나타내기 위해 최대공약수를 이용해야 한다.

 

 

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int GCD(int a, int b) {
	if (a < b) swap(a, b);
	if (a % b == 0) {
		return b;
	}
	else {
		return GCD(b, a % b);
	}
}

bool ch[2001][2001];

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


	int a, b;
	cin >> a >> b;
	int ans = 1;

	for (int i = a; i <= b; i++) {
		for (int j = 1; j < i; j++) {
			int mod = GCD(i, j);
			int a = j / mod;
			int b = i / mod;
			if (ch[a][b] == 0) {
				ans++;
				ch[a][b] = 1;
			}
		}
	}


	cout << ans <<'\n';

	return 0;
}

백준 10166 메모리 및 시간