[BOJ, 백준] 25958 예쁜수 Python

 

 

처음에 문제 이해를 잘못했었는데, 차분히 잘 생각해보니까 어느정도 구조가 눈에 보이기 시작했다.

 

즉, 주어진 "N 이하의 예쁜 수들로" N을 어떻게 만들 수 있을까? 라는 문제가 되겠다.

import math
N, K = map(int,input().split())

pretty_number = []
for i in range (1, N + 1):
    str_i = str(i)
    n = len(str_i)
    summary = 0
    for j in range (n):
        summary += int(str_i[j])
    if i % summary == 0:
        pretty_number.append(i)

dp = [0 for _ in range (0, N + 1)]

for i in range (0, len(pretty_number)):
    dp[pretty_number[i]] += 1
    for j in range (pretty_number[i] + 1, N + 1):
        dp[j] += dp[j - pretty_number[i]]
print(dp[-1] % K)

 

방식 자체는 굉장히 냅색 문제와 유사하게 되겠습니다.