목록long long (1)

승코딩당당당

[C++] 백준 1850: 최소공약수

문제[C++] 백준 1850: 최소공약수 SILVER 1 https://www.acmicpc.net/problem/1850 접근 방법백준 1850번은 두 정수 A와 B가 주어졌을 때, 각각이 1로만 이루어진 수(1111… 형태) 라고 생각하고그 둘의 최대공약수에 해당하는 1의 개수를 출력하는 문제다. 핵심 아이디어는 다음과 같다.111…(A개) 와 111…(B개)의 최대공약수는1이 GCD(A, B)개 있는 수가 된다. 즉,두 수의 최대공약수를 먼저 구하고그 개수만큼 1을 출력하면 된다.따라서 문제의 본질은 두 수의 최대공약수(GCD)를 구하는 것이다.유클리드 호제법을 이용하면 효율적으로 계산할 수 있다.int GCD(ll a, ll b){ if (a % b == 0) return b;..
PS/BOJ 2026. 3. 2. 18:30
이전 Prev 1 Next 다음