백준알고리즘 2485 가로수 [C++]

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

2485번: 가로수

 

 

소스코드

---

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int getGCD(vector<int> diffs){
  int min = diffs.front();
  int i = 0;
  while(1){
    if(diffs[i] % min == 0){
      i++;
    }
      if(i == diffs.size() && *diffs.end() % min == 0) 
        return min;
    else if(diffs[i] % min != 0){
      i = 0;
      min--;
    }
  }
}


int main(){
  int tree, gcd; // 나무의 수, 최대공약수
  int diff, diffsum = 0; // 나무 사이의 거리, 합계
  vector<int> diffs; // 나무 간격 
  vector<int> trees; // 나무 위치
  
  cin >> tree;

  int tmp;
  for(int i = 0; i < tree; i++){
    cin >> tmp;
    trees.push_back(tmp);
  }

  for(int i = 1; i < tree; i++){
    diffs.push_back(trees[i] - trees[i-1]);
    diffsum += (trees[i] - trees[i-1]);
  }
  sort(diffs.begin(), diffs.end());


  cout << "size :" << diffs.size() << endl;
  cout << '\n';
  gcd = getGCD(diffs);

  int res = (diffsum/gcd) - tree + 1;
  cout << res;
}

 

풀이방법

1. 입력받은 나무 사이의 거리를 diffs 벡터에 저장 후 정렬

2. diffs요소의 최대공약수 도출

 

아래의 식을 활용해 최대공약수만 구하면 문제해결이 가능하다. 

 

> 나무 간격의 합 = 최대공약수 x (나무의 수 - 1) + (최대공약수 x 필요나무의 수)

> 나무 간격의 합/최대공약수 - 나무의 수 + 1 = 필요나무의 수

 

코드에 나온 변수로 치환하면

> diffsum = gcd x ( tree - 1 + res)

> res = diffsum/gcd - tree + 1

 

예제 입력을 노트에 옮겨서 먼저 손으로 구해보면 어렵지않게 풀 수 있는 문제였다.