[백준/BOJ] 2485번 가로수 (C/C++)

백준 온라인 저지(BOJ) 2485번 가로수

https://www.acmicpc.net/problem/2485

2485번: 가로수

* 사용언어 : C언어, C++

 

1. 문제

N개의 정수 위치에 이미 가로수가 심어져 있음

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 출력

 

2. 풀이

1) 모든 가로수의 (동일한) 간격 중 최소값 찾기

모든 가로수가 동일한 간격이 되게 하려면

모든 [인접한 두 가로수의 거리]들의 최대공약수를 찾고 해당 값을 간격으로 배치하면 됩니다.

 

숫자 3개 이상의 최대공약수를 찾을 때는

먼저 임의의 2개 숫자로 최대공약수를 계산한 후에

계산된 최대공약수와 3번째 숫자의 최대공약수를 찾으면 됩니다.

 

그리고 4번째, 5번째, ... n번째 숫자 모두 동일한 방식으로

최대공약수와 새로운 숫자의 최대공약수를 찾아주면 됩니다.

 

2) 새로 심어야 하는 가로수 개수 세기

최대공약수를 찾은 후에는 가장 작은 가로수 위치부터 gcd를 반복해서 더하면서 개수를 셀 수 있습니다.

하지만 이 방식은 불필요한 연산을 반복하며 시간 낭비가 생기게 됩니다.

 

저는 계산을 한 번에 하기 위해서 아래 절차로 처리했습니다.

1. 첫 가로수와 마지막 가로수의 사이의 거리를 구함 (pos[i - 1] - pos[0])
2. 그 값을 gcd로 나눈 후 1을 더함 → gcd 간격 배치할 때 필요한 전체 가로수의 개수
3. 전체 개수에서 이미 심어진 가로수 개수(n개)를 뺌 → 새로 필요한 가로수의 개수

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2485_가로수
1892KB	20ms
*/
#include <cstdio>

const int LM = 100000;
int pos[LM], dis[LM], n, gcd, cnt;

int getGCD(int a, int b) {
	if (a < b) {
		int t = a;
		a = b;
		b = t;
	}

	int r;
	while (1) {
		r = a % b;
		if (!r) break;
		a = b;
		b = r;
	}
	return b;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", pos + i);

	for (int i = 0; i < n - 1; ++i)
		dis[i] = pos[i + 1] - pos[i];

	gcd = dis[0];
	for (int i = 1; i < n - 1; ++i)
		gcd = getGCD(dis[i], gcd);

	cnt = (pos[n - 1] - pos[0]) / gcd + 1 - n;
	printf("%d\n", cnt);
	return 0;
}

* !r 은 r == 0 과 동일하게 처리되지만 assembly 단에서 더 간결하게 처리되므로 빠릅니다.