Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • UC++
  • KMP
  • 구현
  • 큐
  • 세그먼트 트리
  • 트라이
  • C++
  • 트리
  • 기하
  • 브루트포스
  • 정렬
  • 투포인터
  • 그래프
  • 문자열
  • LCA
  • 분할정복
  • 스택
  • 유니온 파인드
  • 동적계획법
  • 수학
  • 조합론
  • 백트래킹
  • 이분탐색
  • 백준
  • 정수론
  • 위상 정렬
  • SCC
  • 우선순위큐
  • 최소 스패닝 트리
  • 누적합

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 2981번 문제
공부 및 정리/백준 코드

[C++]백준 - 2981번 문제

2021. 6. 2. 15:40

2981번: 검문 (acmicpc.net)

 

2981번: 검문

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

www.acmicpc.net

 

2981번 : 검문


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

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

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

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

 

입력


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

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

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

 

 

출력


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

 

 


 

생각해 볼 점


나머지가 같은 수를 구하는 문제입니다.

예를 들어 [3, 39, 43]가 있다고 하면, {2, 4}가 정답이 됩니다.

N으로 나누었을 때 모두 동일한 나머지를 가지고 있다는 건 숫자들 간의 차이가 모두 N으로 나누어 떨어진다는 뜻이죠.

 

쉽게 이야기하면,

 

3 과 39의 차이는 36

39와 43의 차이는 4입니다.

 

36과 4의 공약수 모두 정답이 됩니다.

 

다른 예시를 들어볼까요?

 

[61, 83, 711]을 받았을 경우 각 수들 간의 차이는 (22, 628)이고, 이 둘의 공약수는 2 뿐이므로

답은 2 입니다.

 

따라서,

1. 우리는 수를 받아서 숫자들 간의 차이를 구합니다.

2. 해당 차이를 Set에 담습니다. (Set는 자동 정렬과 자동 중복 제거를 수행합니다.)

3. Set안의 숫자들 간의 최대 공약수를 구합니다.

4. 최대공약수의 약수를 검색하여 모두 출력합니다.

 

4번을 수행할 때, 수행 시간을 더 줄이기 위해 2부터 최대공약수의 제곱근까지만 탐색합니다.

 

예를 들어, 최대공약수가 20이면,

 

2에서 20의 제곱근 4까지 반복문으로 검색합니다.

 

for문의 수행 예시

=====================================

2 -------> 20 / 2 = 10 (2, 10은 20의 약수)

3 (약수가 아님)

4 -------> 20 / 4 = 5  (4, 5는 20의 약수)

=====================================

for 문은 총 3번 수행됩니다.

 

2, 10, 4, 5를 set에 담아 차례로 print해주면 완료입니다.

 

코드


#include <iostream>
#include <cmath>
#include <set>
using namespace std;

int gcd(int a, int b)
{
    while(b > 0) // 유클리드 호제법
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    
    return a;
}
int main() {
	int N;
	set<int> interval;
	cin >> N;
	int prev; // 이전 입력
	cin >> prev;
	for(int i = 1; i < N; i++)
	{
        int input;
	    cin >> input;
	    interval.insert(abs(input - prev)); //숫자들의 차이값을 set에 저장
	    prev = input;
	}
	
	set<int>::iterator it = interval.begin();
	int g = *it;
    
	for(;it != interval.end(); it++)	//set 내부의 최대공약수 구하기
	{
	    g = gcd(*it, g);
	}
	
	set<int> result;					//최대 공약수 g의 약수를 담는 set
	result.insert(g);					//자기 자신도 약수이므로 미리 저장
    
	for(int i = 2; i <= sqrt(g); i++)	//g의 제곱근까지만 수행
	{
	    if(g % i == 0)
	    {
	        result.insert(i);			
	        result.insert(g / i);
	    }
	}
	
	for(it = result.begin(); it != result.end(); it++) cout << *it << " ";
	return 0;
}

 

그 외


유클리드 호제법이 자주 쓰이니 항상 암기하도록 합시다.

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 18870번 문제  (0) 2021.06.03
[C++]백준 - 3036번 문제  (0) 2021.06.02
[C++]백준 - 18258번 문제  (0) 2021.05.31
[C++]백준 - 13305번 문제  (0) 2021.05.27
[C++]백준 - 1436번 문제  (0) 2021.05.26
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 18870번 문제
    • [C++]백준 - 3036번 문제
    • [C++]백준 - 18258번 문제
    • [C++]백준 - 13305번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바