[백준 알고리즘] 2981번 : 검문, c++

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

2981번: 검문

c++로 백준 2981번 문제를 풀어보겠다.

 

 

 

 

 

문제

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

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

예제 입력 1 복사

3
6
34
38

예제 출력 1 복사

2 4

 

 

 

 

<문제 풀이>

 

 

처음에 작성한 코드는 다음과 같다.

 

 

 

 

visual studio에서는 원하는 대로 출력됐지만, 백준 사이트에서는 '시간 초과'라고 떴다.

따라서 다시 작성한 코드는 다음과 같다.

위의 문제를 해결하기 위해서는 반복문을 돌려 arr[k] - arr[k-1]들의 최대 공약수를 구해 계산해야했다.

한번에 이해가 되지않아 구글링을 통해 해결했다.

 

 

1. 최대공약수를 구하는 함수를 선언한다.

2. main 함수에서 N값을 입력받고 N개의 정수를 입력받아 배열에 저장한다.

3. 배열에 들어있는 수를 오름차순으로 정리한다.

4. 만든 함수를 통해 최대공약수를 구한다.

5. 나눈 후 나머지 값이 같으면 출력하기 위해 새로운 배열에 그 수를 저장한다.

6. 출력할 값들을 모아둔 배열을 오름차순으로 정리해 하나씩 출력한다.

 

 

 

 

다음에 다시 풀어봐야겠다.