[백준/C++] 2485 가로수

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

2485번: 가로수

코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int gcd(int a, int b)
{
	if (b == 0) return a;
	else return gcd(b, a % b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, result=0;
	cin >> n;
	vector<int> v(n);
	stack<int> gap;
	for (int i = 0; i < n; i++){
		cin >> v[i];
		if (i > 0) gap.push(v[i] - v[i - 1]);
	}

	while (gap.size() > 1)
	{
		int a = gap.top();
		gap.pop();
		int b = gap.top();
		gap.pop();
		gap.push(gcd(a, b));
	}

	int resultGap = gap.top();
	for (int i = 0; i < n - 1; i++) result += (v[i + 1] - v[i]) / resultGap - 1;
	cout << result;
	return 0;
}

 

설명

가로수들 간 간격들의 최대공약수를 구하고 그 최대공약수를 간격으로 가로수를 심으면 되는 문제다.

따라서 main 함수 초반부에서 빠른 입출력을 위한 코드를 작성하고 현재 심어진 가로수의 개수 n을 입력받는다. 가로수의 위치를 저장할 벡터 v와 가로수 간의 간격을 저장할 스택 gap을 생성한다.

반복문을 돌면서 벡터 v에 입력받는 가로수의 위치를 저장하고 스택에 현재 가로수 위치 - 직전 가로수 위치를 한 값을 넣어준다.

반복문이 끝나면 스택의 요소가 하나가 남을 때까지 while문을 돌면서 gcd 함수를 호출해 최대공약수를 구한다. 두 개의 요소를 pop하고 두 요소의 최대공약수를 구해 push하는 과정을 거쳐 모든 간격들의 최대공약수를 구한다. 이때 나는 pop과 push를 이용하고 싶어서 스택을 사용한 것이므로 굳이 스택을 사용하지 않고 다른 방식으로의 풀이도 가능할 것이다.

최종적으로 스택에 남아 있는 하나의 요소가 가로수를 심어야하는  간격이 된다. 벡터 v의 길이-1만큼 반복문을 돌면서 (다음 가로수 위치 - 현재 가로수 위치) / 간격 -1 을 최종 결괏값에 계속 더해나간다.

(예를 들어 간격이 2이고 다음 가로수 위치가 4, 현재 가로수 위치가 2라면 (4-2)/2-1로 이 사이에 심을 가로수는 0개이다.)

최종 결괏값을 출력하고 프로그램을 종료한다.


 

느낀 점

문제를 읽으면서 가로수간 간격들의 최대공약수를 구해야함을 파악했고, 스택을 이용해 최종적인 최대공약수를 구했다.

생각한대로 바로 구현했고 한 번에 통과한 문제다.