백준 13600번
https://www.acmicpc.net/problem/13600

문제

후기

⏰ 풀이시간 30분 ++⏰

번역이 되어있지 않아서 크롬 브라우저로 한국어로 번역하여 풀었다.

입력된 N의 값이 몇개의 Factorial을 더해서 만들 수 있는가에 대한 문제다.

예제 입력1의 10은 3!(6) + 2!(2) + 2!(2) 로

예제 입력2의 25는 4!(24) + 1!(1) 로 만들 수 있다.

에라토스테네스의 체를 풀었던 느낌과 유사하게 접근하였다.

이미 만들어진 Factorial 값들의 합이 list에 들어가 있다면, 그것을 단지 꺼내와서

더해주기만 하면 원하는 값을 찾을 수 있을거라 생각했고, K**0.5로 범위를 좁혔다.

K까지의 Factorial 값들을 ans_li에 미리 append 해둔다음 내림차순으로 정렬하고,

ans_li의 값들을 하나씩 빼오면서 N이 0이 될때까지 뺄 때 마다 cnt를 1씩 더해줬다.

나의 풀이

import sys
input =sys.stdin.readline
import math

N = int(input())
K = int(N ** 0.5)
ans_li= [] 
cnt = 0

for i in range(1,K+1):
    ans_li.append(math.factorial(i))
ans_li.reverse()

while N!=0:
    
    for i in ans_li:

        if N >= i:

            N -= i
            cnt+=1
            break

print(cnt)