문제
백준 BOJ 20003
https://www.acmicpc.net/problem/20003
20003번: 거스름돈이 싫어요
프로불편러 지수는 딱 떨어지지 않는 수는 질색이다. 거스름돈이 남는 것도 딱 질색이다. 지수가 아이템을 사려 하는데, 아이템의 가격은 다 분수로 이루어져 있다. 지금은 가령, 3/2코인을 사려
www.acmicpc.net
사용 알고리즘
풀이
우선 입력받은 값들을 모두 기약분수로 바꾸고
모든 분모들의 LCM을 구해 분모를 먼저 찾는다.
분모들을 LCM으로 통일시켜주면서 분자를 적절한 값을 곱해 수정한다.
분자들의 GCD를 구하면 출력해야 할 답의 분자가 된다.
답의 분자가 항상 1이 나올 것이라고 잘못 생각했다가 조금 헤맸다.
GCD LCM 구할 땐 유클리드 호제법 사용
728x90
'PS > BOJ' 카테고리의 다른 글
| 백준 BOJ 11683 (0) | 2021.06.09 |
|---|---|
| 백준 BOJ 5582 공통 부분 문자열 (0) | 2021.06.08 |
| 백준 BOJ 1027 고층 건물 (0) | 2021.06.07 |
| 백준 BOJ 1812 사탕 (0) | 2021.06.03 |
| 백준 BOJ 17094 Serious Problem (0) | 2021.06.02 |