티스토리 뷰
1188번: 음식 평론가
첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100)
www.acmicpc.net
자기 전에 간단한 문제를 풀고 자려고 골라보았다.
처음에는 n,m 이 각각 홀, 짝 개인 거 또는 gcd와 관련해 식이 달라질 거라 생각하고 몇 개 그려보니, 정답의 식이 다음과 같음을 알 수 있다.
커트 횟수 = m - gcd(n, m)
커트를 최소한으로 해야되는데, 1/gcd(n,m)만큼 자른 것 + a(남은 것) 한 만큼 나눠준다고 생각하면 쉽다.
코드는 다음과 같다.
import math
n, m = map(int,input().split())
print(m - math.gcd(n,m))
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 / 7682 틱택토 C++ (0) | 2021.04.30 |
|---|---|
| 백준 / 6087 레이저 통신 (0) | 2021.04.28 |
| 백준 / 1937 욕심쟁이 판다 C++ (0) | 2021.04.27 |
| 백준 / 1238 파티 C++ (0) | 2021.04.12 |
| 백준 / 1517 버블 소트 C++ (0) | 2021.04.09 |
댓글