[BOJ] 2293번 동전 1 (Python)

📃 문제

[BOJ] 동전 1 🔗링크

오랜만에 DP 문제 도전!
DP는 아직 접근하는 방법이 서툴러서인지, 점화식을 도출해내는게 너무 힘들다.

이 문제를 풀려고 봤더니, 3년 전에 한참 알고리즘을 공부하던 나는 포기했었던 문제였다.
그래서인지 풀고 싶다는 마음이 컸었던 것 같다.

🧠❓ 문제 접근 및 풀이

🐶 1번째 접근

문제에 동전 구성의 경우의 수(제출해야할 답)가 231보다 작다고 나와있어서,
시간복잡도를 고려했을때 완전탐색은 어렵다고 판단했다.

그렇다면 그리디 or DP로 풀 수 있지 않을까?
라고 생각했고, DP를 이용해서 문제를 풀어냈다.

점화식을 간단하게 요약하자면, 아래와 같다
특정 가치를 만들 수 있는 경우의 수
= 이전에 사용한 코인들로 만들 수 있는 경우의 수 + 현재 코인으로 만들 수 있는 경우의 수

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coin = [int(input()) for _ in range(n)]

def ans():
    v = [1] + [0] * (k)

    for c in coin:
        for i in range(c, k+1):
            v[i] += v[i-c]
    print(v[k])

ans()

아, 그리고 나랑 문제 풀이 방법은 같은데 코드 동작 시간이 약 2배 가까이 차이 나서
의아했었는데, 알고보니 전역변수 ↔︎ 지역변수의 차이었다.

Python이 실행될때 전역변수와 지역변수에 접근할때 방식이 다른데,
전역변수를 접근할때 동작이 더 느리다고 한다.

그래서 함수를 만들어 지역변수를 사용하게 했더니 동작 시간이 월등하게 빨라졌다 !.. (184ms → 120ms)
그러니 다른 분들도 참고하시길 바래요 ,,