[BOJ] 2293번 동전 1 / 사용언어 : 파이썬(python)

※ 문제링크 

2293번: 동전 1

해당 문제는 동적 프로그래밍과 관련된 문제로 메모이제이션을 활용하여 풀 수 있는 문제였다. 대다수의 동적프로그래밍 문제와 같이조건을 찾아내고 메모이제이션을 적용할 규칙을 확인하지 못하면 풀 수가 없어서 많이 애를 먹었던 문제였다. 기본적인 개념은 입력받은 숫자들만을 가지고 우선적으로 카운트를 해준다음, 1부터 구해야 하는 범위까지 입력값들을 반복하여 갱신해주는 개념으로문제를풀었다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 리스트에 저장해주고, 카운팅 수를 갱신할 기록용 리스트(dp)를 생성해준다.

2. 입력값들 중 작은 숫자들부터 1부터 k(구해야하는 수)까지 반복문을 돌려 숫자의 경우의 수를 작성해준다.

3. 반복문이 종료된 이후 결과값을 출력한다.

 

n, k = map(int, input().split())
numbers = []
dp = [0 for i in range(k + 1)]
for i in range(n):
    numbers.append(int(input()))

for num in numbers:
    if k - num >= 0:
        dp[num] += 1
    for j in range(1, k + 1):
        if j - num >= 0:
            dp[j] += dp[j - num]
print(dp[k])

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.