2421번 - 저금통 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 586 | 274 | 215 | 46.943% |
문제
홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다.
홍태석은 소수를 좋아하는 것으로 서강대에서 유명하기 때문에, 첫째 저금통에 들어있는 돈의 양과 둘째 저금통의 돈의 양을 이어붙였을 때, 그것이 소수가 되는 것을 너무나도 좋아한다.
예를 들어, 첫째 저금통에 12원이 있고, 둘째 저금통에 7원이 있다고 하자. 그럼 그 두 수를 이은 127은 소수가 된다.
이제, 최대한 소수가 많이 나오도록, 홍태석이 돈을 넣는 최적의 순서를 찾아내면 된다. 가장 처음에 두 저금통에는 1원씩 들어있다.
예를 들어, N=4일 때를 보자.
1,1 → 2,1 → 2,2 → 3,2 → 3,3 → 4,3 → 4,4
위와같이 돈을 넣으면 소수는 오직 1번 등장한다. (43)
하지만, 다음과 같이 돈을 넣으면 소수는 3번 (31,41,43) 등장하게 된다.
1,1 → 2,1 → 3,1 → 4,1 → 4,2 → 4,3 → 4,4
위의 예가 N=4일 때 의 답이다. 가장 처음에 11은 세지 않는다.
입력
첫째 줄에 N이 주어진다. (1<=N<=999)
출력
첫째 줄에 소수가 가장 많이 나오는 저금 방법에서 소수가 나오는 횟수를 출력한다.
예제 입력 1
4
예제 출력 1
3
출처
Olympiad > Baltic Olympiad in Informatics > BOI 2011 P2번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호