CodeDrive

문제:

재현이는 다음과 같은 정수 게임을 하려고 한다. 게임은 다음과 같이 이루어져 있다.

 1. 정수 N과 크기가 K인 배열 A를 정한다.

 2. 1부터 N까지 정수를 모두 종이에 쓴다.

 3. 배열 A의 가장 첫 수를 고르고, 그 수를 배열에서 제거한다. 고른 수를 x라고 했을 때, 종이에 적혀있는 수 중에 x의 배수를 지운다.

 4. 배열이 비어있을 때 까지 3번을 반복한다.

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1<=N<=1,000,000,000, 1<=K<=15)

둘째 줄에 배열 A의 내용이 순서대로 주어진다. 배열에 담겨있는 수는 100보다 작거나 같은 자연수이다.

출력:

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 출력한다.

풀이방법:

포함배제의 원리를 사용해서 풀어야 하는 문제이다. 포함배제의 원리는 유한 집합들의 합집합의 원소를 세는 기법 중의 하나이다. 보통 다음과 같은 식을 가진다.

따라서 count를 통해서 현재 값을 더해야 하는지 빼야 하는지를 결정해준다. 해당하는 값들은 combination으로 만든 조합의 최소공배수 값을 통해서 지워야 하는 갯수를 구할 수 있다.

이렇게 포함배제로 지워지는 수들의 갯수를 구하면 n과 더해줌으로써 남은 개수를 구한다.

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

https://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC