제 4회 생각하는 프로그래밍 대회 C번 - 거스름돈이 싫어요

문제 거스름돈이 싫어요

20003번: 거스름돈이 싫어요

솔루션 및 데이터 Github

Yaminyam/4th-Thinking-PC

---

이번 문제는 내가 좋아하고 자주 출제하는 수학 문제이다.

정수론의 기초중 하나인 유클리드 호제법을 이용하여 풀 수 있다.



불편충인 지수가 아이템을 코인으로 사려고 하는데 거스름돈이 생기는 것을 싫어하여 적당한 코인의 단위를 만들어 분수의 가격을 가지고 있는 아이템들을 거스름돈 없이 살 수 있도록 하는 문제이다.

 

우리는 거스름돈 없이 물건을 구매해야 하므로 새로운 코인단위는 주어진 물건 가격들의 공약수 이어야하고 새로운 코인단위 중 제일 큰 값을 구해야 하므로 최대공약수를 구해야한다.

최대공약수를 구하기 위해 유클리드 호제법을 사용해야 하지만 주어진 수가 분수기 때문에 좀 다르게 생각할 필요가 있다.

 

분수의 최대공약수를 만들기 위해선 분모가 주어진 분수들의 분모들의 최소공배수 이어야하고, 분자는 주어진 분수들의 분자들의 최대공약수 이어야한다.

분모는 작을수록 분자는 클수록 큰 수가 되기 때문이다.

r1 = bunja[0];	//분자
for(int i=1;i<n;i++){
    r1 = gcd(r1, bunja[i]);
}
    
r2 = bunmo[0];	//분모
for(int i=1;i<n;i++){
    r2 = lcm(r2, bunmo[i]);
}

이렇게 새로운 코인단위를 구할 수 있다.

 

하지만 이 문제에는 만족해야하는 몇가지 조건들이 더있다.

주어지는 분수들이 기약분수가 아닐수 도 있다는 조건때문에 최대공약수를 구하기 위해서 먼저 그 분수들을 기약분수로 만들어 주어야 한다.

그리고 문제의 input 조건이 수가 50이어서 굉장히 작아 int범위내에서 처리 될 것 같지만 최대 40개의 숫자들의 최소공배수를 구하게 된다면 엄청나게 큰 숫자가 되게 되므로 long long 형의 타입으로 연산을 해주어야 한다.

 

이 두가지 조건을 잘 캐치해 낼 수 있다면 쉽게 문제를 해결 할 수 있을것이다.

 

사실 기약분수의 조건은 문제를 출제하는 과정에 일부로 의도한 조건이 아닌 문제를 출제하고 보니 생긴 오류였으나 그 오류를 조건으로 설정하여 문제를 한번 더 꼬아버리게 되었다.

그런 조건덕분에 유클리드 호제법 기본문제가 아닌 다른것들 까지 고려해야 하는 문제가 되어 solved.ac 기준 실버1 난이도의 문제가 되었다.