인프런 커뮤니티 질문&답변

초기화를 1로 해야하는 별다른 이유는 없구요, 처음에 문제를 풀 때 dp[0]를 초기화하지 않고 아래와 같이 풀이했었습니다.

for (int i = 1; i <= n; i++)
{
	cin >> temp;
	dp[temp] = 1;
	for (int j = 1; j <= k; j++)
	{
		if (j >= temp) dp[j] = min(dp[j], dp[j - temp] + 1);
	}
}

테스트케이스를 보면 1, 5, 12원짜리 동전을 가지고 15원을 만드는 동전의 개수를 묻는 문제입니다.

dp의 인덱스는 그만큼의 가격을 만들 수 있는 동전의 개수를 저장하기 때문에, 선생님의 풀이는 이미 충분하지만, 기존의 제 풀이였던 dp[1] = 1, dp[5] = 1, dp[12] = 1로 초기화한다면, 중복되는 부분이 있긴 하지만 문제가 없을 것이라 판단하여 넣어봤었습니다.

선생님께서 주신 예시인 dp[3] = 3인 경우에 dp[3] = 1로 다시 초기화하면 문제가 될 수 있다고 말씀해주셨지만, 제가 생각할 때 그런 경우는 없다고 생각합니다. 제가 잘못생각하고있다면 알려주시면 감사하겠습니다 :)

안녕하세요 유태님 ㅎㅎ

아 제가 생각을 잘못했네요. 네 이 경우 최솟값인 1로 초기화를 해도 됩니다.

혼란을 드려 죄송합니다.

그리고 이렇게 하시면 됩니다.

#include<bits/stdc++.h>
using namespace std; 
int n, k,a[10001], temp, INF = 987654321;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    cin >> n >> k; 
    fill(a, a + 10001, INF);
    a[0] = 0; 
    
    for(int i = 0; i < n; i++){
        cin >> temp; 
        if(temp <= 10000)a[temp] = 1;
        for(int j = temp; j <= k; j++){
            a[j] = min(a[j], a[j - temp] + 1);
        }
    }
    if(a[k] == INF) cout << -1 << "\n"; 
    else cout << a[k] << "\n"; 
    return 0;
}

감사합니다.

감사합니다 ^^