백준 2293: 동전 1 - javascript(dp)

문제 출처 

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

 

정답 풀이 

주의 : js로는 메모리 초과가 난다. 

 

아래와 같이 2차원 그래프를 만들어줄 것이다. 

세로 줄에는 동전의 가치 

가로 줄에는 가치의 합이다. 

그리고 각 그래프 안에는 해당 동전과 이전 동전으로 해당 합을 만들 수 있는 경우의 수를 구할 것이다. 

 

우리는 저 빨간 부분을 return 해주면 된다. 

 

 

 

아래 같은 경우에는 

1 동전으로 1의 가치를 만들 수 있는 경우의 수는 1이다. (1 동전 1개)

1 동전으로 8의 가치를 만들 수 있는 경우의 수는 8이다. (1 동전 8개) 

 

그리고 아래와 2동전으로 가치의 합의 경우의 수를 구할 때, 

가치의 합 2부터 생각해주면 된다. 왜냐하면 동전 2로는 가치 1을 만들 수 없기 때문임 ! 

그렇기 때문에 그냥 1동전으로 가치 1 만들 수 있는 경우를 그대로 내려주면 된다. 

 

아, 근데 생각해보니, 합 0을 만들어주는 경우의 수도 만들어주는 것이 좋겠다. 

그래서 아래와 같이 표를 왼쪽에 하나 더 추가해줬다. 

그 이유는 다음에 나온다. 

아래 빨간 부분은 어떻게 구할까? 

1과 2로 합 8을 구하는 경우의 수를 구하는 부분이다. 

이는 1로만 합 8을 구하는 경우 + 2로 합 6을 구하는 부분 이 된다. 

- 1로만 합 8을 구하는 경우 : (이 부분을 이해가 갈 것이다)

- 2로만 합 6을 구하는 부분 : 동전 2 그 자체로 합 8중에 2를 차지하므로 그 가치를 뺀 6을 구하는 경우의 수를 가져온다. 

 

 

 

예시) 

실제 합 8을 구하는 경우 수 

- 1로 합 8을 구하는 수 : 1+1+1+1+1+1+1+1 = 8 

- 1과 2로 합 6을 구하는 수 : 

1+1+1+1+1+1

1+1+1+1+2 

1+1+2+2

2+2+2

 

이것만 이해하면, 사실 이제 코드만 작성해주면 되는데, 우리가 고쳐줘야 할 부분이 있다. 

빨간색 부분을 봐보자. 

저 부분은 

- 1로 2구하는 경우의 수 

- 2로 0을 구하는 경우의 수 

를 더하는 값이 된다. 그럼 1  

 

그런데 이상하다 ?

1과 2로 합 2를 만들 수 있는 경우의 수는 

- 1+ 1 

- 2 

이렇게 두개가 되어야 한다. 

이 간극을 없애주기 위해서 

 

사실, 동전 2로 합 0을 만들 수 있는 경우의 수도 하나인 것이다. 아예 안쓰는 경우 하나 !!! 

동전 1,2,5로 합 0을 만들 수 있는 경우의 수도 마찬가지로 하나다. 아예 안쓰는 경우 하나 !!! 

아래와 같이 1로 채워주자. 

 

그리고, 나머지 부분을 다 채워보자 ! 

초록색 부분은, 해당 동전을 합쳐서는 안되기 때문에 이전 동전까지의 경우의 수를 그냥 내려받는 부분이다. 

답은 10이 된다. 

 

정답 코드 

위에 설명하기 위해 2차원 배열로 나타냈는데, 

코드 구현은 1차원 배열로 나타냈다. 

잘 생각해보면, 계속 수를 갱신하기 때문에 가능하다. 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,k] = input.shift().map(v => +v); 
input = input.map(el => +el)

function solution(n,k, input){
    const dp =  new Array(k+1).fill(1)

    dp[0] = 1; 
    
    for(let i=0; i<n; i++){
        for(let j=input[i]; j<k+1 j++){
            dp[j] = dp[j] + dp[j- input[i]] 
        }
    }
    return dp[k]
    }

console.log(solution(n,k,input))

 

 

저 식은 안될 것 같고, 

아래와 같은 식이 되어야 하지 않나 ? 싶다. 

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,k] = input.shift().split(' ').map(v => +v); 
input = input.map(v => +v); 

const dp = Array.from({length: n}).map(() => new Array(k+1).fill(0)); 
for(let i=0; i<n; i++){
    dp[i][0] = 1
}

for(let i=0; i<n; i++){
    for(let j=1; j<k+1; j++){
        if(input[i] > j) dp[i][j] = dp[i-1][j]
        else{
            dp[i][j] = dp[i-1][j] + dp[i][j-input[i]]   
        }
    }
}

console.log(dp[n-1][k])

 

 

백준 2293번 '동전 1' 문제를 해결하려는 접근에서 몇 가지 오류와 최적화할 수 있는 부분들이 있습니다. 현재 코드에서는 dp 배열의 정의와 인덱스 처리가 문제를 일으킬 수 있습니다. 다음과 같은 문제들을 고려해 볼 수 있습니다:

문제점 1: dp 배열 정의 방식

현재 코드에서 dp 배열은 n x (k+1) 크기로 정의되어 있습니다. 하지만 동전의 개수는 동전 종류에 대한 것이지, 동전 종류 수만큼의 DP 테이블을 만들 필요는 없습니다. 1차원 배열로도 충분히 문제를 해결할 수 있습니다.

문제점 2: 첫 번째 동전만을 처리하지 않음

dp[i][j] = dp[i-1][j] 구문에서 i-1이 음수가 될 수 있습니다. i=0일 때, dp[-1][j]는 정의되지 않기 때문에 문제가 발생할 수 있습니다. 이 문제는 동전 종류를 고려하는 방식에서 잘못되었습니다.

문제점 3: DP 배열 초기화

dp[i][0] = 1은 잘못된 초기화입니다. dp[j]에서 dp[0]만을 1로 초기화해야 합니다. 왜냐하면 동전이 0원이 되는 경우는 아무 동전도 사용하지 않는 경우 딱 하나뿐이기 때문입니다.

개선된 해결 방법:

dp 배열을 1차원 배열로 정의하고, 동전의 값을 하나씩 순차적으로 처리하며, dp를 업데이트하는 방식으로 코드를 수정할 수 있습니다.

수정된 코드:

개선된 코드 설명:

1. 1차원 DP 배열: dp[j]는 j원을 만들 수 있는 방법의 수를 의미합니다.
2. 초기화: dp[0] = 1로 초기화하여, 0원을 만드는 경우는 아무 동전도 사용하지 않는 경우 단 하나임을 나타냅니다.
3. 동전별로 DP 업데이트: 각 동전에 대해 coins[i]부터 k까지의 금액에 대해 dp 값을 업데이트합니다. dp[j]는 dp[j - coins[i]]의 값에 해당 동전이 추가된 경우의 수를 더해줍니다.
4. 중복 방지: 한 동전이 여러 번 중복되서 처리되지 않도록 동전의 가치가 작은 것부터 큰 것 순서로 처리하며, 각 동전이 독립적으로 처리되도록 합니다.

이 방식은 문제에서 요구하는 최적의 방법으로, 시간 복잡도는 O(n * k)입니다. 이는 충분히 효율적이며 n과 k의 범위 내에서 성능을 보장합니다.

출력 예시:

dp[k]는 k원을 만드는 모든 경우의 수를 출력하게 됩니다.