[백준/C++] 3036번: 링

• 문제

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

3036번: 링

 

• 코드

#include <iostream>
#include<vector>
#include <set>
#include <algorithm>
#include <deque>
using namespace std;

int main() {
int n = 0;
cin >> n;
vector <int> arr;
int srr[100][2];
int a = 0;
for (int i = 0; i < n; i++) {
cin >> a;
arr.push_back(a);
}
int b = 0;
for (int i = 0; i < n - 1; i++) {
b = arr[i+1];
if (arr[0] < b) {
int flag = 1;
int ar = arr[0];
while (flag == 1) {
flag = 0;
for (int j = 2; j < arr[0] + 1; j++) {
if (ar % j == 0 && b % j == 0) {
ar /= j;
b /= j;
flag = 1;
}
}
}

srr[i + 1][0] = ar;
srr[i + 1][1] = b;


}
else if (arr[0] > b) {

int flag = 1;
int ar = arr[0];
while (flag == 1) {
flag = 0;
for (int j = 2; j < b + 1; j++) {
if (ar % j == 0 && b % j == 0) {
ar /= j;
b /= j;
flag = 1;
}
}
}
srr[i + 1][0] = ar;
srr[i + 1][1] = b;
}
else {
srr[i + 1][0] = 1;
srr[i + 1][1] = 1;
}
}
for (int i = 0; i < n - 1; i++) {
cout << srr[i + 1][0] << "/" << srr[i + 1][1] << endl;
}

}

• 풀이

경우의 수를 잘 나누어야하는 문제였다. 그리고 기약분수로 나타내기 위해 최대공약수로 끝까지 나누기 위해 while문을 사용해야 했다.