[백준] No.2293 동전 1 01

 

2293번: 동전 1

 

N개의 서로 다른 동전이 주어질 때, 동전을 이용해서 K를 만들 수 있는 경우의 수는 몇 개인가? 묻는 문제이다.

예를 들어서 동전이 1, 2, 3 있고 K는 5라고 가정해보자.

1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 2+3해서 4가지가 있다.

 

와... 처음에 문제를 받았을 때, 살짝 이게 뭐지 싶었다.

받을 수 있는 동전의 개수도 다른데, 동전의 가치도 입력마다 달라진다..?

확실한 건 memoization을 통해서, 빠른 연산을 하는 종류라는 감이 왔다.

 

그럼 DP이고, 1차원 배열로는 문제를 해결할 수 없을 것 같았다.

2차원 배열을 생성하고, 첫 번째 index는 N(coin), 두 번째 index는 K로 잡았다.

DP를 풀면서 느낀 건데, dp[N][K]나 dp[N] 같은 게 무엇을 의미하는지, 정확하게 정의해야 나중에 헷갈리지 않는다.

고민하다가 "N번째 코인까지 사용했을 때, K를 만들 수 있는 경우의 수"로 정의했다.

 

예를 들어서 코인이 1, 2, 3 있고, K가 7이라고 해보자. 그럼 위와 같은 표를 그릴 수 있다.

색칠한 3개의 회색 칸을 자세하게 살펴보자. 왼쪽에서부터 순서대로 살펴본다.

가장 왼쪽 회색은 dp[1][2]로 표현할 수 있다. 해석하면, 코인 1을 가지고 2를 만들 수 있는 경우의 수다.

중앙의 회색은 dp[3][4]로 표현할 수 있다. 해석하면, 코인 1, 2, 3을 가지고 4를 만들 수 있는 경우의 수다.

가장 오른쪽 회색은 dp[2][6]로 표현할 수 있다. 해석하면, 코인 1, 2를 가지고 6을 만들 수 있는 경우의 수다.

이제 대충 표는 그릴 수 있으니 예제 입력으로 가보자.

 

값을 채워넣은 것은 규칙을 발견해서 채운 게 아니라, 규칙을 찾기 위해 직접 계산하였다.

검은색 숫자는 dp[N][K]를 의미하고, 빨간색 숫자 A + B에서 A는 dp[N-1][K]를, B는 새로 생긴 경우의 수이다.

30개 칸에서 마지막 칸을 채웠을 때, 비로소 규칙을 찾을 수 있었다.

 

dp[3][10]이라고 할 때, 두 가지를 더해야 한다.

1. 1, 2로 10을 만들 수 있는 경우의 수. A+B에서 A([N-1][K])에 해당한다.

2. 1, 2, 5로 새롭게 10을 만들 수 있는 경우의 수. A+B에서 B에 해당한다.

2번의 케이스를 반대로 생각해보면, 코인을 똑같이 사용하면서 10을 만들기 이전의 상황을 생각하면 된다.

즉, 1, 2, 5로 5를 만들 수 있는 경우에 5가 하나 더 생긴 것이다.

5를 coin이라고 하면, [N][K-coin]의 위치를 더하면 되는 것이다.

 

for i, coin in enumerate(coins, 1):
    for k in range(1, K+1):
        dp[i][k] += dp[i-1][k] + dp[i][k-coin]

이 부분을 함수로 나타내면 이렇다. coins는 동전의 가치를 저장한 list이다.

enumerate로 index(i)와 coin을 반복해서 받아온다.

그리고 1부터 K까지 하나하나 채워나간다. dp[i-1][k] + dp[i][k-coin] 식을 따라서.

 

# ---------- Main ----------
N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]

이제 코드를 작성해보자. N, K, coins를 받아오는 코드다.

 

# ---------- Main ----------
dp = [[0] * (K+1) for _ in range(N+1)]

for i in range(1, N+1):
    dp[i][0] = 1

2차원 dp를 [N][K] 담을 수 있는 공간만큼 선언해준다.

그리고 각 row에서 첫 번째 인덱스는 1로 초기화해준다.

1로 초기화 해주는 이유는 동전을 한 개만 쓰는 경우 때문이다.

 

예를 들어 [2][2]라고 해보자. 그럼 [2-1][2]와 [2][2-2]를 더해야 한다.

[2-1][2]는 [1][2]로 1 동전을 가지고 2를 만드는 경우의 수다(A).

[2][2-2]는 [2][0]로 2 동전을 가지고 0을 만드는 경우의 수다(B).

즉, B에서 [K]가 0인 경우는 동전 하나만 경우의 수에 새로 추가되는 케이스다.

 

[3][5]일 때, 5를 새롭게 만들 수 있는 경우의 수는?

5 동전 하나만을 사용하는 것이다. 즉 [3][5-5]의 값은 1로 초기화해두어야 한다.

 

# ---------- Main ----------
for i, coin in enumerate(coins, 1):
    for k in range(1, K+1):
        dp[i][k] += dp[i-1][k] + dp[i][k-coin]

위에서 언급한 핵심 아이디어 코드이다.

 

0 >>> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1 >>> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2 >>> [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
5 >>> [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]

코드를 완성하고 예제 입력을 넣어 출력한 dp이다.

올바르게 2차원 배열을 생성했음을 알 수 있다. 그럼 dp[-1][-1]이 최종 답이 된다.

 

TLE가 아니라 MLE가 떴다? 문제 조건을 살펴보았다. N 최댓값 100, K 최댓값 10,000, coin 최댓값 100,000.

생각보다 값이 그렇게까지 크지 않다고 생각했다. 1,000,000(백만) 개의 칸이면 충분히 할 수 있지 않나?

객체 공간을 선언하는 거라서 값이 0이나 100,000이나 이건 상관없을텐데...

 

최악의 경우로 메모리를 테스트해보았다. 엥? 8 MB밖에 안 쓰는데?

하지만 어림도 없지! 문제 조건으로 4 MB 제한 걸어버리기!

예전에 DP 문제를 풀 때, 굳이 2차원으로 선언을 하지 않았던 방법이 있다.

내 코드 상에서 row 각 줄을 한 줄 한 줄 돌기 때문에 1차원 공간에서도 충분히 해결 가능하다고 생각했다.

 

dp = [0] * (K+1)
dp[0] = 1

for coin in coins:
    for k in range(coin, K+1):
        dp[k] += dp[k-coin]

print(dp[-1])

우선 dp를 K+1만큼만 1차원으로 선언해주었다. 0번째 index를 반복문으로 초기화할 필요도 없어졌다.

코드에서 필요한 것은 결국 dp에서 가장 마지막 값 뿐이다. 앞에 불필요한 부분도 탐색은 생략했다.

예를 들어서 coin이 5라면, K가 1부터 4까지는 탐색할 필요가 없다. 따라서 range 시작을 coin부터 한다.

당연히 1차원 배열로 줄었으니 더하기 연산도 dp[k-coin]으로 줄었다.

 

생각보다 간단한 리팩토링을 거쳐서 AC를 받을 수 있었다.

살짝 난이도 있는 DP를 풀고 싶다면 적당한 문제라고 생각한다.

 

P.S.1

살짝 사족을 붙이자면, 이번에 작성할 세 문제는 좋은 느낌이었다.

2293번_동전, 2493번_탑, 1461_도서관으로, 각각 DP, stack, greedy로 알고리즘 분류도 다 달랐다!

알고리즘이 전부 다 달라서 생각하는 맛이 있었고, 난이도도 적당했다.

엄청 쉽지도 않으면서 그렇다고 감이 안 올 정도로 어렵지도 않은, 적당히 타오를 수 있는 그런 문제들.

 

실제로 '대충 흐름이 이러면 될 거 같은데?' 느낌이 오고, 직접 손으로 적어가며 확인해보았다.

결국 1시간만에 3문제를 모두 풀 수 있었다.

문제당 20분인 셈이니, 코테에 점점 다가가는 기분이 들어 살짝 상기됐다.

머리로만 어어 이렇게 되나? 고민하기보다는 확실히 적어가면서 생각하는 게 효과적이다.

생각하면서 막히던 것이 바로 뚫려버렸다. 

 

마지막으로, 불과 몇 달 전까지만 해도 실버 1~2 문제를 풀 때 엄청나게 허덕였다.

지금은 어떤가. 골드 4~5 문제를 풀면서, '오, 이정도면 적당한데?'라는 느낌을 받았다.

20230822 기준으로 동전_46.4%(26257/56568), 탑_31.7%(21374/63821), 도서관_47.6%(4275/8923)이다.

물론 정답률을 보면 알겠지만 그렇게 어려운 문제는 아니었다. 그럼에도 이 느낌은 중요하다.

매일 노력해도 내가 잘하고 있는지 확인할 수 없어서 멈추는 경우가 정말 많으니까.