카테고리 없음

[백준 2981 파이썬/ 자바] 검문

은행장 노씨 2021. 2. 10. 02:06

오늘은 내가 재밌게 풀었던 문제를 포스팅하겠다.

속에 들어있는 개념들도 재밌고, 풀어가는 과정도 흥미로웠다.

처음 구상을 하기가 어려웠다. 반례를 찾기 위해 공책으로 디버깅을 하면서 문제를 풀었다. 

 

 

 

 "게임을 시작하지!"

 

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

2981번: 검문

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간

www.acmicpc.net

1. 문제 읽기

 

 

문제는 간단했다.

입력된 수 모두를 나눴을 때 나머지가 같은 수를 오름차순으로 출력하라.

2. 개념 정리

 처음에는 이렇게 생각했다. 입력된 수들을 수열리스트라고 하자.

 

1. 수열리스트의 최대공약수를 구하면 나머지가 0일 것이다.

2. 나머지가 다른 수를 구하면 그 수의 배수는 다 나머지가 다르다.

3. 나머지 판별 함수를 만든다. 나머지를 구해서 리스트에 넣고 set으로 바꾼다.(개수가 1이면 나머지가 같다.)

 

이렇게 생각하고 true/false 리스트를 만들었다.

인덱스가 수라고 가정하고 나머지가 하나인지 판별해서 코드를 짰다.

제출했다. 시간초과가 났다.

 

다시 갈아엎고  나머지가 같은지 알아내는 법을 구글링 했다.

그러다 보니 고1 수학과정에 나머지정리를 배울 때 썼던 개념을 알게 되었다.

 

2 - 1. 나머지가 같은 수 구하기

 

 

이 방법을 이용하면 나머지가 같은 수를 알 수 있다.

위의 방법은 두 개의 수가 있을 때 사용할 수 있다.

 

수열 리스트 차 모두로 최대공약수를 구하면 나머지가 같은 수를 구할 수 있다.

 

그리고 최대공약수의 약수들을 오름차순으로 정렬하면 된다!

 

2 - 2. 유클리드 호제법

이제 문제를 풀기 위해 gcd(최대공약수)를 구하는 법을 공부하겠다. 소인수분해를 하는 것은 비효율적이다.

사실 파이썬은 대박 똑똑하기 때문에 최대공약수를 구하지 않고 import 해서 쓰면 된다.

하지만 나는 자바로도 풀 거기 때문에 유클리드 호제법을 보겠다. (참고로 1학년 이산수학 때 배웠다.)  

1. 두 수를 쓴다.
2. 두 수의 몪과 나머지를 적는다.(몪은 큰 수 옆에 나머지는 밑에 적는다.)
3. 한쪽 수가 0이 나오면 멈춘다.
4. 0이 아닌 다른 수가 최대공약수이다.

이렇게 보면 생각하기 어려우니까 예시를 들겠다.

 

 

 

 

이런 방법으로 최대공약수를 구한다. 식을 작성하면 이렇게 된다.(자바)

 

1
2
3
4
5
6
public static int euclidGCD(int x, int y){
    if (y == 0)
        return x;
    else
        return euclidGCD(y, x % y);
}

 

자, 이제 문제를 풀어보자!

3. 코드 작성

나는 파이썬이 편하기 때문에 파이썬으로 식을 먼저 작성했다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from math import gcd
import sys
input = sys.stdin.readline
 
n = int(input())
nums = [] #입력 받을 수 리스트
for _ in range(n):
    nums.append(int(input()))
 
gcd_value = abs(nums[1] - nums[0]) 
for i in range(2,n): #가장 작은 gcd값을 구한다.
    gcd_value = gcd(abs(nums[i] - nums[i - 1]), gcd_value)
 
answer = [gcd_value]
 
for i in range(2, int(gcd_value ** 0.5) + 1): #gcd약수를 구한다
    if gcd_value % i == 0:
        answer.append(i)
        answer.append(gcd_value//i)
 
answer = list(set(answer))
print(" ".join(map(str, sorted(answer)))) #정렬하고 출력
 
 
 

 

 

맞았다 오예!

 

 

자바로도 풀어봤다.

자바는 기억이 잘 안나서 꽤 힘들었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
import java.io.*;
 
public class Main {
 
    public static int euclidGCD(int x, int y){
        if (y == 0)
            return x;
        else
            return euclidGCD(y,x % y);
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int [] nums = new int[n];
        for (int i = 0; i < n; i++)
            nums[i] = Integer.parseInt(br.readLine());
 
        int gcd_value = Math.abs(nums[1] - nums[0]);
        for (int i = 2; i < n; i++)
            gcd_value = euclidGCD(gcd_value, Math.abs(nums[i] - nums[i - 1]));
 
        ArrayList <Integer> answer = new ArrayList<Integer>();
        answer.add(gcd_value);
        double half = Math.sqrt(gcd_value);
        for (int i = 2; i < (int)half + 1; i++)
            if (gcd_value % i == 0) {
                answer.add(i);
                answer.add(gcd_value/i);
            }
 
        TreeSet<Integer> ans = new TreeSet<Integer>(answer);
        ArrayList<Integer> a = new ArrayList<Integer>(ans);
        StringBuilder sb = new StringBuilder();
        for (Integer i : a){
            sb.append(i).append(" ");
        }
        System.out.println(sb.toString());
    }
 
}

 

 

야호!

 

자바에서 앞으로 유용하게 쓸 정보를 메모해놔야겠다.

* list 중복값 제거하기
> HashSet으로 바꾸고 다시 list로 바꾼다.(정렬하고 싶으면 TreeSet이용)

 

끝!