結果
問題 |
No.1737 One to N
|
ユーザー |
![]() |
提出日時 | 2024-10-08 17:26:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 515 bytes |
コンパイル時間 | 599 ms |
コンパイル使用メモリ | 82,028 KB |
実行使用メモリ | 78,080 KB |
最終ジャッジ日時 | 2024-10-08 17:26:32 |
合計ジャッジ時間 | 3,881 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
def make_divisors(n): lower_divisors , upper_divisors = [], [] i = 1 while i*i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] N = int(input()) dp = [1 << 60] * (N + 1) dp[1] = 0 for i in range(1, N + 1): for k in range(2, N + 1): if i * k > N: break dp[i * k] = min(dp[i * k], dp[i] + k) print(dp[N])