백준#3036

★☆☆☆☆☆☆☆☆☆

문제 접근방식

---

첫 번 재원이 돌면 나머지가 몇 바퀴를 도느냐를 출력하는 문제이므로 첫 번 재원의 지름만큼 나머지 원이 돈다고 생각했다. 원의 지름 공식은"2πr"인데 r을제 외하 곤 세원이 공통으로 들어가니 지름도 구할 필요 없이 작은 원의 반지름/큰 원의 반지름이 도는 바퀴수가 된다. 기약 분수로 출력하라고 했으니 약분만 해주면 간단한 문제이다.

int den, num; //분모 분자

	for (int i = 1; i < _r.size(); i++) {
		num = _r[0]; //첫번째원
		den = _r[i]; //else
		if (num % den == 0) { //분모 분자가 나누어 떨어질때
			cout << num / den << "/" << 1 << "\n";
		}
		else {
			(num > den) ? GCD(num, den) : GCD(den, num);
			num /= GCD_; //최대공약수로 나누어줌
			den /= GCD_;
			cout << num << "/" << den << "\n";
		}

	}

 

 시간 복잡도: O(n)이다, 왜냐하면 n이 입력었을때 for문이 n-1번 실행되고 for문 안에 있는 연산들이 상수 시간에 처리되기 때문이다.