[BOJ 23364 // C++] Almost Always

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 23364번 문제인 Almost Always이다.
문제는 아래 링크를 확인하자.

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

23364번: Almost Always

Birthday Problem에 대해 알고 있다면 쉽게 접근할 수 있을 문제이다. Birthday Problem이란 다음과 같다:

Q) 1년이 365일로 고정되어있다고 가정할 때, 최소 몇 명이 모여야 이중 생일이 같은 사람이 있을 확률이 50% 이상이 될까?
A) 23명이 모이면 그중 생일이 같은 사람이 있을 확률이 50% 이상이 된다.

더 자세한 내용은 영문 위키피디아(링크)를 참고하자.

 

이를 확장하면 주어진 50만개의 독립적으로 뽑힌 수들 중에는 중복되는 수가 있을 확률이 매우 높다는 것을 유추할 수 있다. 또한 동일한 두 수는 약수와 배수 관계를 만족하므로 이러한 두 수는 문제에서 요구하는 답중 하나가 된다.

 

따라서, 단순히 주어진 50만개의 수 가운데 중복된 수가 있는지를 탐색하는 것으로 문제를 매우 높은 확률로 통과할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int N;
map<int, int> mp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		if (mp.find(x) == mp.end()) mp.insert(make_pair(x, i));
		else {
			cout << mp[x] << ' ' << i;
			return 0;
		}
	}
}