[Baekjoon] 2485번: 가로수

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

2485번: 가로수

 

최대공약수의 개념을 활용하는 문제인데, 단순히 최대공약수를 구하라고 한다면 모두 빠르게 프로그래밍으로 구현할 수 있지만 이렇게 서술형 문제로 나오면 왠지 모르게 어떤 방법으로 풀어야할 지 헷갈리는 것 같다.

 

---

 

문제 해결 과정

착안

가로수의 간격이 등간격이 되도록 새로운 가로수를 심는 과정은 주어진 간격을 등분하는 것과 같으므로, 각 간격들 사이의 공약수(common divisor)만큼 등분하도록 가로수를 심는 것과 같다. 이때, 가로수를 최대한 적게 심는다는 것은 곧 최대공약수를 구하라는 것과 동일한 문제로 바꾸어 풀 수 있게 된다. 최대공약수(greatest common divisor, GCD)는 이전 포스트에서와 같이 유클리드 호제법(Euclidean algorithm)을 통해 구하였다.

 

1. \(i\)번째 가로수가 심어져 있는 위치를 \(P(i)\)라고 하면, \(1\)번째 가로수부터 \(N\)번째 가로수 까지 심어져있는 가로수들 사이의 모든 간격 즉 \(P(2)-P(1),  P(3)-P(2), ..., P(N)-P(N-1)\) 전체에 대한 최대공약수$$GCD_{N} = GCD(P(2)-P(1), P(3)-P(2), ..., P(N)-P(N-1))$$를 구한다.
2. 처음 가로수와 마지막 가로수 사이의 길이 \(P(N)-P(1)\)를 \(GCD_{N}\)로 나눈 결과에 1을 더한 값은, 동일한 간격으로 가로수가 모두 심어졌을 때의 총 개수이다.
3. 새로 심어질 가로수의 위치와 관계 없이 수량만 구하면 되므로, 2.에서 구한 값으로부터 현재 심어져 있는 가로수의 수 \(N\)를 뺀다.

 

구현

현재 심어져 있는 가로수의 개수(\(N\))가 많을 수록, 한 번에 모든 간격을 구해서 저장한 다음 다시 반복문을 통해 최대공약수를 구하게 되면 오랜 시간이 소요된다(\(O(N)\)의 과정을 반복해서 수행하는 것). 따라서 앞 단계에서 구한, \(1\)번째 가로수부터 \(i-1\)번째 가로수까지 등간격으로 나누기 위한 최대공약수$$GCD_{i-1} = GCD(P(i-1)-P(i-2), P(i-2)-P(i-3), ..., P(2)-P(1))$$와 \(P(i)-P(i-1)\) 사이의 최대공약수 \(GCD_{i}\)를 구하고, 이 값을 그대로 사용하여 다음 단계에서의 가로수 사이의 간격과 또다시 최대공약수를 과정과 같이 점진적(progressive)인 방법으로 구현해보았다(설명으로는 좀 어려운 점이 있어서... 주석 참고ㅠ). 아래 코드에서 next 변수의 의미가 조금 모호하여 이해하기 어려울 수도 있지만 마땅한 좋은 이름이 생각나지 않아서 next라고 지었다...

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
	while (b)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main()
{
	int N;
	int start;
	int next;
	int temp;

	scanf("%d", &N);
	scanf("%d", &start);
	scanf("%d", &next);
	
    	// 가장 처음 두 가로수 사이의 간격 P(2)-P(1)을 저장
        // 이름을 gcd_dist로 정한 이유는 이 값이 결국 최대공약수로 바뀌기 때문.
	int gcd_dist = next - start;
	for (int i = 2; i < N; i++)
	{
		// temp: i번째 가로수 위치 입력
		scanf("%d", &temp);
        
		// 이전 단계에서 구한 최대공약수 gcd_dist와 현재 i번째, i-1번째 가로수 사이의 간격 temp 사이의
		// 최대공약수를 구하여 다음 단계에서 이용하기 위해, 변수를 다시 초기화 해준다.
		gcd_dist = GCD(temp - next, gcd_dist);
		next = temp;
	}
	
	printf("%d\n", (next - start) / gcd_dist + 1 - N);

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.

 

---

 

처음 문제를 풀 때에는 모든 가로수들 사이의 간격을 전부 구하여 저장하고 다시 반복문을 돌려 간격 사이의 최대공약수를 구했는데, 굳이 그렇게 계산하지 않아도 점진적으로 계산이 가능해서 코드를 수정했고, 결과적으로는 실행 속도의 향상이 있었다.