[C++] 백준 3036번 링

1. 문제이해

3036번: 링 (acmicpc.net)

3036번: 링

 

상근이는 N개의 링을 이용해 각각의 링들이 앞에 있는 링과 겹쳐지도록 놓았다.

상근이가 첫 번째 링을 한바퀴 돌릴 때, 나머지 링은 몇 바퀴 돌아가는지

기약분수 형태로 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

첫 번째 링을 기준으로, 첫 번째 링이 한바퀴를 돌 때,

나머지 링들이 몇바퀴를 도는지를 기약분수 형태로 나타내야 한다.

링이 한바퀴를 도는데 걸리는 시간은 링의 반지름과 비례하므로,

이 점을 유의하고 예제를 보면 다음과 같다.

 

<예제 입력 2>

첫 번째 링의 반지름은 12, 나머지 링들의 반지름은 3, 8, 4 이다.

링이 도는 시간은 링의 반지름과 비례하므로,

각 링들이 한바퀴를 도는 데 걸리는 시간을 12t, 3t, 8t, 4t 라고 둘 수 있다.

 

이제 첫 번째 링과 나머지 링들을 살펴보면,

첫번째 링이 한 바퀴 도는 12t동안, 한 바퀴 도는데 3t가 걸리는 링은 12t / 3t = 4 / 1바퀴를 돌 수 있다.

 즉, 첫 번째 링이 한 바퀴를 도는 동안 해당 링은 4 / 1 바퀴를 돌게 된다.

한 바퀴를 도는데 8t, 4t가 걸리는 링들은 12t동안 각각

12t / 8t = 3 / 2 바퀴, 12t / 4t = 3 / 1 바퀴를 돌게 된다.

즉, 첫 번째 링이 한 바퀴 도는 동안 나머지 링들은

(첫 번째 링의 반지름 / 해당 링의 반지름) 만큼 돌게 된다.

 

그렇다면 이 분수를 기약분수로 나타내려면 어떻게 해야할까?

답은 간단하다. 바로 두 반지름의 최대공약수로 나누어주면 된다.

예를 들어, 위의 예제의 12 / 8 의 경우에도, 두 수의 최대공약수인 4로 나누어주면

기약분수인 3 / 2 로 나타낼 수 있다.

최대공약수를 구하는 방법은 유클리드 호제법을 이용했다.

 

유클리드 호제법을 이용해 최대공약수를 구하는 문제는 이전에 다뤄본 적이 있는데,

자세한 내용은 아래 포스팅을 참조하자.

https://beginnerdeveloper-lit.tistory.com/2

[C] 백준 2609번 최대공약수와 최소공배수

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

// 유클리드 호제법 이용 (최대공약수) 
int Euclidean(int a, int b) {
	int r = a % b;

	if (r == 0) {
		return b;
	}
	else {
		return Euclidean(b, r);
	}
}

int main() {
	int N;           // 링의 개수
	int R;           // 기준이 되는 첫번째 링의 반지름 
	int ring[100];   // 나머지 링들의 반지름
	int gcd;         // 두 링의 반지름의 최대공약수

	cin >> N;
	cin >> R;
	for (int i = 0; i < N - 1; i++) {
		cin >> ring[i];
	}
	
	for (int i = 0; i < N - 1; i++) {
		gcd = Euclidean(R, ring[i]);  // 두 수의 최대공약수 구하기
		cout << R / gcd << "/" << ring[i] / gcd << endl;
	}

	return 0;
}

위 소스코드를 보면, 메인함수 전에 우선 최대공약수를 구하는 함수를 구현했다.

최대공약수를 구하는 함수는 유클리드 호제법을 이용해 구현했다.

 

메인함수에서 위와 같이 변수들을 설정하고,

링의 개수와 첫 번째 링의 반지름(R)을 입력받은 뒤,

나머지 링들의 반지름을 배열 ring[i]에 저장해주었다.

 

for문을 통해 첫 번째 링의 반지름인 R과 나머지 링들 ring[i]에 대해

차례로 최대공약수(gcd)를 구하고,

(첫 번째 링의 반지름 / 해당 링의 반지름) 을 구해주었다.

이때, 기약분수로 나타내야 하므로, 각 값을 최대공약수로 나누어 출력했다.

 

 

---

프로그래머스 SQL 테스트 SELECT 부분을 풀어보고 다시 백준으로 돌아왔다.

(SQL 테스트도 꾸준히 올릴예정이다.😊)

문제를 여러개 풀어보면서 느끼는건데,

예전에 풀었던 개념들이 다른 문제에 쓰이는 경우가 참 많은 것 같다.🤔