21395번 - 연속한 소수 만들기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 111 | 44 | 40 | 72.727% |
문제
Albert는 최근 소수 (prime)에 대해 배웠다. 1보다 큰 양의 정수 p의 약수가 1과 p뿐인 경우 p를 소수라 한다. 만약 n개의 소수 p[1], p[2], ..., p[n] 이 아래 조건을 만족하면 이는 "연속한 소수" 라고 한다:
- p[1], ..., p[n]이 n개의 고유한 (서로 다른) 소수이며
- min(p[1], ..., p[n]) <= q <= max(p[1], ..., p[n]) 을 만족하는 모든 정수 q에 대해 q가 소수이면 p[1], ..., p[n]중 하나와 같다.
예를 들어 [5, 3, 2, 7]과 [11, 7, 5, 13]은 연속한 소수이며 [2, 5, 7]이나 [5, 13, 17] 혹은 [2, 2, 3, 5]는 연속한 소수가 아니다.
Albert는 혼자 할 수 있는 놀이를 생각하던 중, 소수 만들기 라는 게임을 해보기로 했다.
먼저 임의의 양의 정수 n개를 선택한다 (편의상 x[1], x[2], ..., x[n] 이라 하자). 이를 연속한 소수 n개로 바꾸고 싶은데, 아래와 같은 제약이 따른다.
- 각 정수 x[i]를 임의의 소수로 바꿀 수 있고, x[i]가 이미 소수인 경우라도 다른 소수로 바꿀 수 있다. (x[i]가 이미 소수인 경우, 바꾸지 않아도 된다.)
- 어떤 정수 y를 임의의 소수 p로 바꾸는데 | p - y | 만큼의 벌점이 발생한다.
예를 들어 n = 3 이고 x = [7, 13, 3]이라 하자.
- 이미 모든 수가 소수이지만, 연속한 소수가 아니다.
- 이 세 정수를 [5, 7, 11]로 바꾸는 경우 벌점은 |5 - 7| + |7 - 13| + |11 - 3| = 16이 발생한다.
- 다른 방법으로, x[2]를 13에서 11로 바꾸고 (벌점 2 발생) x[3]을 3에서 5로 바꾸면 (벌점 2 발생) 총 벌점은 4가 발생하고, 결과로 [7, 11, 5]를 얻게 되는데 이는 연속한 소수이다 (순서는 상관 없음에 유의하자).
다른 예로, n = 3 이고 x = [2, 2, 2]라 하자.
- 가령 첫 수를 3으로 바꾸고 마지막 수를 5로 바꾸면 벌점이 4 발생하고 결과로 [3, 2, 5]를 얻게 된다.
입력으로 Albert가 처음에 고른 n개의 정수 x[1], ..., x[n]이 주어졌을 때, 이를 n개의 연속한 소수로 바꾸기 위해 필요한 최소한의 벌점을 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 나누어 주어지는데 첫 줄에 n이 주어지고 다음 줄에 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해 입력으로 주어진 정수를 연속된 소수로 바꾸기 위해 필요한 최소한의 벌점을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 200
- 1 ≤ x[i] ≤ 100,000 (1 ≤ i ≤ n)
예제 입력 1
4 3 2 2 2 4 5 7 12 12 3 7 13 3 7 74 79 7 16 46 68 71
예제 출력 1
4 2 4 106
예제 1: 본문에서 다루었다
예제 2: 추가 설명 없음
예제 3: 본문에서 다루었다
예제 4: 입력으로 주어진 정수를 다음 7개의 고유한 소수로 바꾸는 경우를 생각해보자: 73 79 53 59 61 67 71 이 때 벌점은 1 + 0 + 46 + 43 + 15 + 1 + 0 = 106으로 최소가 된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호