정리
백준 19699번: 소-난다! 본문
백준 19699번: 소-난다!
19699번: 소-난다!
지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 하늘을 날 수 있다는 사실을 깨달았다. 이 사실이 퍼지자 소들은 다시 자유롭게 하늘을 날기 시작했다.
www.acmicpc.net
조합과 소수판별법을 사용하면 풀 수 있는 문제이다
- 소들의 무게를 리스트에 저장한다
- 파이썬 라이브러리를 사용하여 나올 수 있는 모든 조합을 구한다
- 각 조합의 합이 소수인지 아닌지 판별한다. 소수이면 출력을 위한 리스트에 저장한다
- 소수를 모아놓은 리스트에서 중복된 항목을 제거하기 위해서 set으로 변환한 뒤 다시 list로 바꾸어 sort한다
- 리스트의 길이가 0이면 -1을 출력한다. 그 외에는 리스트의 항목을 순서대로 출력한다
아래 더보기는 소수판별법에 대한 내용
더보기
소수를 판별하는 법은 간단하다.
N을 [2, √N] 까지 나누어 보면 된다
만약 위 범위 내에서 N이 정수로 나누어 떨어진다면 N은 소수가 아닌 것이다
시간복잡도는 O(√N) )이다.
'Programming > 백준 BOJ' 카테고리의 다른 글
| 백준 13335번: 트럭 (0) | 2021.02.02 |
|---|---|
| 백준 1669번: 멍멍이 쓰다듬기 (0) | 2021.01.13 |
| 백준 1339번: 단어 수학 (0) | 2021.01.11 |
| 백준 1251번: 단어 나누기 (0) | 2021.01.11 |
| 백준 1654번: 랜선 자르기 (0) | 2021.01.05 |
'Programming/백준 BOJ' Related Articles
more
Comments