< 백준 BaekJoon : 2485번 가로수> C++

<<문제>>
https://www.acmicpc.net/problem/2485

2485번: 가로수

 

이어지는 숫자의 배열을 같은 간격으로 만들기 위해 몇개의 숫자가 더 필요한지 찾는 문제입니다. 

 

처음에는 거리차 중에 Optimal 간격이 있을 것이라고 잘못 판단해 시간이 좀 걸렸네요.

 

결국 핵심은, 이어지는 숫자들의 간격들에서 최대공약수를 찾아 간격을 맞춰주는 것입니다. 

 

 

 

<<코드>>

#include <iostream>
using namespace std;

void swap(int &numA, int &numB) {
  int temp = numA;
  numA = numB;
  numB = temp;
}

int makeGcd(int numA, int numB) {
  if (numB > numA)
    swap(numA, numB);

  int numC;
  while (1) {
    numC = numA % numB;
    if (numC == 0) {
      break;
    } else {
      numA = numB;
      numB = numC;
    }
  }

  return numB;
}

int main() {
  int numTree;
  cin >> numTree;

  int distanceList[numTree - 1];
  int distance;

  // 지난 위치
  int lastLocation;
  // 현재 위치
  int nowLocation;

  // 초기값 설정
  cin >> lastLocation;
  cin >> nowLocation;
  distance = nowLocation - lastLocation;
  distanceList[0] = 0;
  distanceList[1] = distance;
  lastLocation = nowLocation;

  for (int i = 2; i < numTree; i++) {
    cin >> nowLocation;

    distanceList[i] = nowLocation - lastLocation;

    distance = makeGcd(distance, distanceList[i]);

    lastLocation = nowLocation;
  }

  int temp;
  int result = 0;
  for (int i = 1; i < numTree; i++) {
    temp = distanceList[i] / distance;
    // cout << distanceList[i] << distance << temp << endl;
    if (temp != 1) {
      result += (temp - 1);
    }
  }

  cout << result;
}

 

방법이야 여러가지가 있겠지만 최대공약수를 통해 간격을 찾아내는 것이 핵심이네요.

 

그걸 생각 못하면 좀 어려울 듯