• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 2293번 : 동전 1 with python3

22 Sep 2018

Reading time ~1 minute

https://www.acmicpc.net/problem/2293

import sys
read = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x)+ "\n")

n,k = map(int, read().split())
a = [0]+[int(read()) for _ in range(n)]
d = [1]+[0]*(k)
for i in range(1,n+1):
    for j in range(a[i], k+1):
    # 일단 여기왔을 때는 이 수 보다 작은 것들은 다 이미 채워져 있다.
    # a가 작은 순으로 들어왔다고 가정하면
        d[j] += d[j-a[i]]
        # 이건 일정 간격으로 횟수를 더하기 위해 만든 것
        # 나의 의문은 1 씩 느는 것은 알겠는데 2(a[i]의 예)씩 느는 것은 어쩌냐 였는데
        # a[i]씩 뺀 것을 더하기 때문에 2(a[i]의 예)씩 느는 것이 채워진다.
        # a[i]보다 작은 것은 어차피 할 필요 없고 수의 끝까지 해야하기 때문에
        # 범위는 (a[i], k+1)이다.
print(d[k])


success

d[i][j] j번째 동전까지 시행

첫 번째 동전만 썼을 경우의 수를 다 만들고 그다음에 첫번째와두번째 동전만 썼을 경우의 수를 다 만들고 이런식으로 순차적으로 가는 것이다.

success

import sys
read = lambda : sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x)+ "\n")

n, k = map(int, read().split())
d = [[0]*(101) for _ in range(1001)]
c = [0]+[int(read()) for _ in range(n)]

for i in range(n+1):
    d[i][0] = 1
    # 기본값 0으로 만들기

for i in range(1, n+1):
    for j in range(1, k+1):
        if j-c[i] < 0:
          # 만들고자 하는 가격이 coin가격보다 작으면 넣는 것이다.
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = d[i-1][j] + d[i][j-c[i]]
write(d[n][k])


참고자료 http://learn-programming.tistory.com/28



algorithm백준 Share Tweet +1