정수론 및 조합론 - 3036번

2월 7일(화) - 정수론 및 조합론(3036번)

3036번: 링

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 첫 번째 링의 반지름은 고정인 상황에서, 그 뒤에 나오는 여러 원의 반지름과의 최대공약수를 각각 구한다

- 각각 구한 최대공약수를 이용해서, "첫 링의 반지름 / 최대공약수" 와 "i번째 링의 반지름 / 최대공약수" 두 값을 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

int main(void)
{
	int first, second;
	scanf("%d %d", &first, &second);

	int g_c_d = 0;
	for (int i = 1; i <= first && i <= second; i++)
	{
		if (first % i == 0 && second % i == 0) {
			g_c_d = i;
		}
	}

	printf("%d\n", g_c_d);
	printf("%d", first * second / g_c_d);

	return 0;
}

1. 최대공약수를 구하는 식은 위의 2609번 문제에서의 풀이를 활용하려했으나, 계산과정이 너무 복잡해짐

-> 검색결과 유클리드 호제법이라는 알고리즘을 재귀함수와 반복문을 이용해서 구현가능하다는 것을 새로 알게됨

-> 최대공약수를 구하는 과정을 간단하게 바꿈

-> https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=pgh7092&logNo=221141884885

C언어 유클리드 호제법(Euclidean Algorithm) 구현하기(최대공약수 / GCD)

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int Euclidean(int a, int b)
{
	if(b == 0)
	{
		return a;
	}
	else
	{
		return Euclidean(b, a % b);
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);

	int r_of_ring[100];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &r_of_ring[i]);
	}

	int g_c_d;
	for (int i = 1; i < n; i++)
	{
		g_c_d = Euclidean(r_of_ring[0], r_of_ring[i]);
		printf("%d/%d\n", r_of_ring[0] / g_c_d, r_of_ring[i] / g_c_d);
	}
	
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ