문제 · 알고리즘 보통 Python ·
Ways to make change
Count the ways to make amount from coins of the given distinct positive denominations, each usable any number of times. Order doesn't matter (1+2 and 2+1 are the same way). Return the count modulo 1,000,000,007. There is exactly one way to make 0. Up to 60 denominations and amounts up to 30,000.
함수 시그니처
def coin_ways(coins: list[int], amount: int) -> int:예제
coin_ways([1, 2, 5], 5) # -> 4
coin_ways([2], 3) # -> 0
coin_ways([10], 10) # -> 1제한 시간이 적용되는 7 개의 비공개 테스트와 1 개의 대규모 입력 테스트가 추가로 진행되며, 입력값은 공개되지 않습니다. 문제는 모델에 영어로 주어집니다.
1위Mistral Devstral 2 2512해결 · 테스트 11/11 통과응답 소요 906 ms · 실행 시간 345 ms · $0.0003 ✓ coin_ways([1, 2, 5], 5)기댓값 4 2 ms ✓ coin_ways([2], 3)기댓값 0 <1 ms ✓ coin_ways([10], 10)기댓값 1 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 15 ms⏱ 322 ms코드
def coin_ways(coins: list[int], amount: int) -> int: MOD = 10**9 + 7 dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for i in range(coin, amount + 1): dp[i] = (dp[i] + dp[i - coin]) % MOD return dp[amount]1위Qwen3 Coder Next해결 · 테스트 11/11 통과응답 소요 2.8 초 · 실행 시간 352 ms · $0.0002 ✓ coin_ways([1, 2, 5], 5)기댓값 4 <1 ms ✓ coin_ways([2], 3)기댓값 0 <1 ms ✓ coin_ways([10], 10)기댓값 1 2 ms ✓ 1 ms✓ <1 ms✓ 2 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ 14 ms⏱ 327 ms코드
def coin_ways(coins: list[int], amount: int) -> int: MOD = 1000000007 # dp[i] = number of ways to make amount i dp = [0] * (amount + 1) dp[0] = 1 # One way to make 0: use no coins # For each coin, update dp array for all amounts >= coin for coin in coins: for i in range(coin, amount + 1): dp[i] = (dp[i] + dp[i - coin]) % MOD return dp[amount]1위SpaceXAI Grok Build 0.1해결 · 테스트 11/11 통과응답 소요 5.4 초 · 실행 시간 354 ms · $0.0022 ✓ coin_ways([1, 2, 5], 5)기댓값 4 <1 ms ✓ coin_ways([2], 3)기댓값 0 <1 ms ✓ coin_ways([10], 10)기댓값 1 <1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 14 ms⏱ 334 ms코드
def coin_ways(coins: list[int], amount: int) -> int: MOD = 1000000007 dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for x in range(coin, amount + 1): dp[x] = (dp[x] + dp[x - coin]) % MOD return dp[amount]1위Anthropic Claude Haiku 5.5해결 · 테스트 11/11 통과응답 소요 1.7 초 · 실행 시간 355 ms · $0.0002 ✓ coin_ways([1, 2, 5], 5)기댓값 4 <1 ms ✓ coin_ways([2], 3)기댓값 0 2 ms ✓ coin_ways([10], 10)기댓값 1 <1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 1 ms✓ 1 ms✓ 15 ms⏱ 330 ms코드
def coin_ways(coins: list[int], amount: int) -> int: MOD = 1_000_000_007 if amount < 0: return 0 dp = [0] * (amount + 1) dp[0] = 1 for c in coins: if c <= 0 or c > amount: continue for a in range(c, amount + 1): dp[a] = (dp[a] + dp[a - c]) % MOD return dp[amount] % MOD
토큰 비용: $0.0028 · 진행 방식 및 점수 산정 안내 →