https://www.acmicpc.net/problem/2485
문제
직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.
입력
첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.
풀이 과정
이번에도 공약수를 사용하여 푸는 문제다. 가능한 한 가장 적은 나무를 균일한 간격으로 심어야한다. 균일하게 가능한 한 가장 적은 나무이므로 최대 공약수를 구하면 될 것 같다.
입력으로 주어지는 1, 3, 7, 13의 간격들을 구해보면 3-1 = 2, 7-3 = 4, 13-7 = 6이다. 2, 4, 6의 최대 공약수는 2이므로 1, 3, 7, 9, 11, 13으로 나무를 심는다면 균일하게 심어진다는 것을 알 수 있다.
다음은 java를 사용한 풀이이다.
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
// 총 가로수 개수
int N = Integer.parseInt(br.readLine());
// 가로수 위치
int[] location = new int[N];
// 처음과 끝에 심어져있는 가로수 위치
int firstTree,lastTree;
// 간격의 최대 공약수
int division = 1;
// 총 가로수 수
int count = 0;
for( int i = 0; i < N; i++ ){
int num = Integer.parseInt(br.readLine());
location[i] = num;
}
firstTree = location[0];lastTree = location[N-1];
// 간격 구한 후 대입
for( int i = 0; i < N-1; i++ ){
location[i] = location[i+1] - location[i];
}
// 최대 공약수 구하기
for( int i = 2; i <= location[0]; i++ ){
boolean hasDivision = true;
for( int j = 0; j < N-1; j++ ){
if( location[j] % i != 0 ){
hasDivision = false;
break;
}
}
// 공약수를 가졌다면 현재 공약수를 i로 저장
// 루프 중 마지막에 저장된 값이 최대공약수
if( hasDivision )
division = i;
}
int i = firstTree;
while( lastTree >= i ){
count++;
i += division;
}
// 결과 출력
// 총 가로수 수 - 현재 가로수 수
System.out.println(count - N);
}
}최대 공약수는 아래 반복문을 사용해서 구하였다. 마지막 처음의 가로수부터 마지막 가로수 위치까지 i로 나눈 나머지가 0이라면 i는 공약수이다. 그리고 마지막에 division 변수에 저장된 i가 최대 공약수이다.
for( int i = 2; i <= location[0]; i++ ){
boolean hasDivision = true;
for( int j = 0; j < N-1; j++ ){
if( location[j] % i != 0 ){
hasDivision = false;
break;
}
}
// 공약수를 가졌다면 현재 공약수를 i로 저장
// 루프 중 마지막에 저장된 값이 최대공약수
if( hasDivision )
division = i;
}간과한 부분이 한가지 있다. 모든 간격에 대한 공약수를 구하게끔 로직을 작성하였는데, 애초에 아래 이미지와 같은 조건이 있기에 가로수 세 개만 있어도 그 간격을 구할 수 있다.
즉, 가로수 3, 5, 9이 있다면 간격은 2, 4이다. 그리고 2, 4의 최대 공약수가 간격의 기준이 된다.
