문제:
재현이는 다음과 같은 정수 게임을 하려고 한다. 게임은 다음과 같이 이루어져 있다.
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과 더해줌으로써 남은 개수를 구한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
from itertools import combinations
from math import gcd
def LCM(N):
l=1
for i in N:
l=l*i//gcd(l,i)
return l
n,k=map(int,input().split())
A=list(map(int,input().split()))
unions=0
for count in range(1,k+1):
for N in combinations(A,count):
l=LCM(N)
unions+=(-1)**count*(n//l)
print(n+unions)
|
cs |
문제링크:
https://www.acmicpc.net/problem/14848
14848번: 정수 게임
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ K ≤ 15) 둘째 줄에 배열 A의 내용이 순서대로 주어진다. 배열에 담겨있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
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
포함배제의 원리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 조합론에서, 포함배제의 원리(包含排除의原理, 영어: inclusion–exclusion principle)는 유한 집합들의 합집합의 원소를 세는 기법 중의 하나이다. 조합론에서 널리 쓰이는 근본적인 기법이며, 이에 대하여 조합론자 잔카를로 로타는 다음과 같이 평했다. “ 유명한 포함배제의 원리는 이산 확률론과 조합론에서의 열거 문제에서 가장 유용한 기법 가운데 하나이다. 잘 적용하면, 이 원리를 사용하여 수많은 조합론적
ko.wikipedia.org
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1010. 다리 놓기 (0) | 2019.11.06 |
|---|---|
| [BOJ]1495. 기타리스트 (0) | 2019.11.05 |
| [BOJ] 1325. 효율적인 해킹 (0) | 2019.10.31 |
| [BOJ]7569. 토마토 (0) | 2019.10.30 |
| [BOJ]7576. 토마토 (0) | 2019.10.29 |