반응형
BOJ10787.java - 숨바꼭질을 최단횟수로 진행하기
술래가 s에 있고, 여러명의 사람을 d칸씩 이동하면서 잡아야 할 때
d칸씩 이동해서 잡을 수 있다는 것은 떨어져있는 거리가 d칸의 배수라는 뜻이다.
즉, 술래와 각 사람의 거리차이를 모두 구해서 GCD를 구한다.
import java.util.Scanner;
public class BOJ10787 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int t=n;
int s=sc.nextInt();
int gcd=Math.abs(s-sc.nextInt());
while(--t>0){
int gap=Math.abs(s-sc.nextInt());
gcd=GCD(gap,gcd);
}
System.out.println(gcd);
}
static int GCD(int a, int b){
while(b!=0){
int r=a%b;
a=b;
b=r;
}
return a;
}
}
반응형
'Coding Test(Algorithms)' 카테고리의 다른 글
[JAVA] 백준 수학 연습문제 - BOJ 2004 (0) | 2021.07.12 |
---|---|
[JAVA] 백준 수학 연습문제 - BOJ 2089 (0) | 2021.07.11 |
[JAVA] 백준 수학 연습문제 - BOJ 17103 (0) | 2021.07.09 |
[JAVA] 수학 연습문제 - 백준 6588 (0) | 2021.07.08 |
[JAVA] 수학 연습문제 - 백준 10872 (0) | 2021.07.07 |