💡문제
양의 정수는 서로 다른 소수의 합으로 나타낼 수 있다. 두 정수 n과 k가 주어졌을 때, n을 서로 다른 k개의 소수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 여기서 덧셈의 순서만 다른 경우(3+5, 5+3)는 모두 1가지로 센다.
예를 들어, n=24, k=3일 때, 2가지로 나타낼 수 있다. {2, 3, 19}, {2, 5, 17} 합이 24가 되는 서로 다른 소수 3개는 이 2가지를 제외하고는 없다. 또, n=24, k=2일 때 답은 {5, 19}, {7, 17}, {11, 13} 3가지이며, n=2, k=1일 때 답은 {2} 1가지이다. n=1, k=1일 경우에는 1은 소수가 아니기 때문에 답은 0이다. 마지막으로 서로 다른 2개 소수의 합이 4가 되는 경우도 없기 때문에, n=4, k=2도 답이 0이다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각각의 테스트 케이스는 한 줄에 n과 k가 공백으로 구분되어 있다. (n ≤ 1120, k ≤ 14)
출력
각 테스트 케이스에 해당하는 경우의 수를 한 줄에 하나씩 출력한다. 정답은 항상 2^31보다 작다.
예제입력
12
24 3
24 2
2 1
1 1
4 2
18 3
17 1
17 3
17 4
100 5
1000 10
1120 14예제출력
2
3
1
0
0
2
1
0
1
55
200102899
2079324314📖내가 작성한 Code
import sys
"""
소수를 모든 데이터 중에 가장 큰 값에 맞추어 동적으로 소수 전부 찾기
그리고 그 리스트의 k개 합한 것이 최소가 되는 거임
뒤로 하나씩 맞춰보기
"""
def find_sum_prim_number(n, k, array):
dp = [[0] * (n+1) for _ in range(k+1)]
dp[0][0] = 1
for i in array:
for cnt in range(k, 0, -1):
for j in range(n, i-1, -1):
dp[cnt][j] += dp[cnt-1][j-i]
return dp
def find_prim_number(num):
is_prim = [0, 0] + [1]*(num - 1)
for i in range(2, int(num**0.5) + 1):
if is_prim[i]:
for j in range(2*i, num + 1, i):
is_prim[j] = 0
prim_number = [i for i in range(2, num + 1) if is_prim[i]]
return prim_number
def main():
inputs = [int(n) for n in sys.stdin.buffer.read().split()]
n, k = [], []
for num in range(1, 2 * inputs[0], 2):
n.append(inputs[num])
k.append(inputs[num + 1])
prim_number = find_prim_number(max_n := max(n))
dp = find_sum_prim_number(max_n, max(k), prim_number)
sys.stdout.write("\n".join(map(str, [dp[k[num]][n[num]] for num in range(inputs[0])])))
if __name__ == "__main__":
main()
✍️풀이과정
이제 소수 문제는 거진 에라토스테네스의 체로 하면 됨. 그런데 배낭 문제 같이 0/1 문제와 결합된 문제라서 조금 고민함. 이때 소수가 두번 쓰이면 안되니까
for i in array:
for cnt in range(k, 0, -1):
for j in range(n, i-1, -1):
dp[cnt][j] += dp[cnt-1][j-i]이렇게 거꾸로 해야했는데, 처음에는 그냥 돌아서 오류 났었음. 순방향인지 역방향인지 잘 보고 하자.
그리고, 푼사람이 얼마 없는지
python3 기준 시간 1등함 ㅎㅎ
🧠 코드 리뷰
-
함수 및 변수 네이밍: 함수 이름 및 변수 이름을 조금 더 직관적으로 수정하면, 코드의 가독성이 높아집니다. 예: find_prim_number → generate_primes, find_sum_prim_number → count_prime_sums
-
코드 주석 보완: 각 함수의 목적과 알고리즘의 핵심 부분에 대한 주석이 추가되면, 다른 사람이 코드를 이해하는 데 도움이 될 것입니다.
🛠️AI 개선 코드
import sys
from typing import List
def generate_primes(max_value: int) -> List[int]:
"""
Sieve of Eratosthenes 알고리즘을 사용하여 max_value까지의 소수를 생성합니다.
:param max_value: 소수를 구할 최대 값
:return: 2 이상 max_value 이하의 소수 리스트
"""
is_prime = [False, False] + [True] * (max_value - 1)
for i in range(2, int(max_value ** 0.5) + 1):
if is_prime[i]:
for j in range(i * 2, max_value + 1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]
def count_prime_sums(target: int, count: int, primes: List[int]) -> List[List[int]]:
"""
dp[i][j]는 i개의 서로 다른 소수를 사용하여 합이 j가 되는 경우의 수를 나타냅니다.
:param target: 소수들의 합으로 만들고자 하는 최대 값
:param count: 선택할 소수의 개수 최대치
:param primes: 사용 가능한 소수 리스트
:return: dp 테이블
"""
dp = [[0] * (target + 1) for _ in range(count + 1)]
dp[0][0] = 1 # 아무 소수도 선택하지 않은 경우, 합이 0인 유일한 경우
for prime in primes:
# 소수를 중복 사용하지 않도록 소수의 개수를 역순으로 업데이트합니다.
for used in range(count, 0, -1):
for sum_val in range(target, prime - 1, -1):
dp[used][sum_val] += dp[used - 1][sum_val - prime]
return dp
def main():
# 모든 입력 데이터를 정수 리스트로 읽어옵니다.
data = list(map(int, sys.stdin.buffer.read().split()))
test_cases = data[0]
targets, counts = [], []
# 각 테스트 케이스는 목표 합(target)과 사용 소수 개수(count)로 이루어집니다.
for i in range(test_cases):
targets.append(data[2 * i + 1])
counts.append(data[2 * i + 2])
max_target = max(targets)
max_count = max(counts)
# 에라토스테네스의 체를 이용해 최대 목표값까지의 소수를 생성합니다.
primes = generate_primes(max_target)
# 동적 계획법(DP) 테이블을 미리 계산합니다.
dp = count_prime_sums(max_target, max_count, primes)
output_lines = []
for i in range(test_cases):
output_lines.append(str(dp[counts[i]][targets[i]]))
sys.stdout.write("\n".join(output_lines))
if __name__ == "__main__":
main()
💻결과
🖱️참고 링크
