[Leet code - 322] Coin Change ❌

문제

Input : 정수배열 coins, 정수 amount

Output : coins 원소의 합으로, amount를 만들 수 있는 최소한의 동전 개수 반환, 만들 수 없다면 -1 반환

※ 각 원소는 여러 번 제한 없이 사용 가능하다.

 

 

시간 복잡도

※1초에 1억번을 대략적인 기준으로 삼는다.

 

사실 보자마자 n을 어떤 걸로 해야 할지 감이 안 잡혔다.

그래서 계획 수립 후 n을 구했다.

 

 

해결 계획

먼저 0부터 amount까지 최소값을 저장해가면서 진행할까 고민을하다가,

amount가 최대 10,000인걸 확인 후에 메모제이션을 사용하기로 확정지었다.

 

아래의 코드와 같은 느낌으로,  하나의 인덱스에서 모든 코인 값을 더해 점차 채워가는 방식으로 하면 될 것 같았다.

FOR each coin in coins
	dp[i] = dp[i - coin[0]];

 

이렇게 식이 어느정도 나온 후에 복잡도를 구할 수 있었다.

$O(n) = amount * coins.size = 10'000 \times 12 = 120'000$

이정도면 지금 진행하려는 방법은 충분히 통과가 가능하다.

 

그 후에 어떻게 채워갈지 좀 더 자세하게 생각했다.

그 중에 먼저 채워넣은 값이 최소값이 유지가 가능한가? 이게 핵심이였는데,

나는 몇 번 해보고 유지가 되네? 하고 넘어갔지만, 해당 케이스가 존재함을 풀이 포기 후에야 알았다.

 

그 후에 수도코드를 작성했다.

//초기값 설정
Fill dp with 0

FOR each element in coins
    dp[element] = 1

//메모제이션
FOR (i <- coins[0] TO amount)
{
    // 만들 수 없으면 넘어간다, 만들 수 없으면 0으로 계산하고 마지막에 -1로 변경한다.
    IF (dp[i] == 0) CONTINUE

    // 만들 수 있으면 다음 것들을 추가함
    FOR each element in coins
    {
        // 값이 없으면 새로 삽입
        IF (dp[i + element] == 0)
            dp[i + element] = dp[i] + 1

        // 이미 값이 있으면 최소값 구하기
        ELSE
            dp[i + element] = min(dp[i + element], dp[i] + 1)
    }
}

IF (dp[amount] == 0) return -1
return dp[amount]

이 후에 몇번 시뮬레이션을 돌려보고 구현에 들어갔다.

 

 

구현(오답)

int coinChange(vector<int>& coins, int amount) {

    if (amount == 0 )return 0;

    // 초기값 설정
    int dp[10001] = {0};

    for (auto& data : coins)
    {
        dp[data] = 1;
    }

    // 메모제이션
    for (int i = coins[0]; i < amount; ++i)
    {
        // 만들 수 없으면 넘어간다, 만들 수 없으면 0으로 계산하고 마지막에 -1로 변경한다.
        if (dp[i] == 0) continue;

        // 만들 수 있으면 다음 것들을 추가함
        for (int data : coins)
        {
            // 기존에 값이 들어있으면 넘어간다.
            if (0 < dp[i + data]) continue;
            dp[i + data] = dp[i] + 1;
        }
    }

    // 출력
    if (dp[amount] == 0) return -1;
    return dp[amount];
}

 

 

되돌아보기

핵심 식은 잘 파악한 거 같은데, 디테일을 잘 못 살렸던 것 같다.

먼저 채워진 값이 최솟값이다

성립하지 않았다, 왜냐하면 정렬이 되었다는 가정은 없기 때문이다.
사실 정렬문제는 어느 정도 생각했는데, 정렬이 되어 있지 않을까?라는 먼가 이때는 왜 이렇게 생각했지?
암튼 안일해서 틀렸다.

 

Out of bound

$coins[i] \le 2^{31}-1$에 대해 더 고려하지 못했다.

for (int data : coins)
{
    // 기존에 값이 들어있으면 넘어간다.
    if (0 < dp[i + data]) continue;
    dp[i + data] = dp[i] + 1;
}

이 부분에서 data[$2^{31} + \alpha$]가 나올 수 있게 됨으로 Out of bound가 발생하게 되었다.

 

그래서 아래처럼 amount 이상의 값은 넘어가는 식으로 해결했어야 했다.

for (int data : coins)
{
    if (amount < data) continue;
    ...
}

하지만 더 좋은 방법이 있었다.

Backward DP

지금처럼 dp[i + ?]로 미래의 값을 채워넣는게 아닌,
dp[i - ?]식으로 과거의 값을 참조하여 DP를 채워 넣으면 Out of bound가 발생할 확률이 매우 낮아진다!

해당 방법은 다음에 적용해 봐야겠다.

 

개선 코드

나중에 다시 풀어보고 작성한다.