백준 - 동전2 , 제곱수의 합

dp유형중 헷갈리는 유형을 정리해보려고 급하게 쓴다.

 

이런 유형들의 문제는 착각하기 쉬운게 가장 적게 사용하도록 만들라고 해서

조건에 해당하는것중에서 가장 큰거부터 골라나가면 가장 적게 사용하고 구해지겠지? 라고 착각하는것이다.

 

말이 이상한데 풀어말하자면

동전2 같은 경우에는 

동전 종류 3개 이것들을 사용해서 합 15를 만드는데  동전을 가장 적게 사용할때를 구하는건데

 

동전 종류중에서 12원이 가장 크므로 12를 선택해버리면 남는 3원은 1원짜리 3개로 채워야하기 때문에

동전을 4개 써야하는데  이건 최소가 아니다.

5원동전 3개를 쓰면 해결되기 때문.

 

이런 오류를 범해서는 안된다.

 

아래는 제곱수의 합 코드

#include <stdio.h>
 
int main(void){
    
    int N;
    int Dp[100001] = {};
    scanf("%d", &N);
    
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j*j <= i; j++){
            if (Dp[i] > Dp[i - j*j] + 1 || Dp[i] == 0)
                Dp[i] = Dp[i - j*j] + 1;
        }
    }
    
    printf("%d\n", Dp[N]);
 
    return 0;
}


출처: https://wootool.tistory.com/102 [우투리와툴툴]

 

아래는 동전2 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int arr[101];
int dp[100001];

int main()
{
	int n;
	int sum;
	cin >> n;
	cin >> sum;
	for (int i = 1;i <= n;i++) {
		cin >>arr[i];
	}
	for (int i = 1;i <= sum;i++) {
		dp[i] = 100001;
	}
	dp[0] = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = arr[i];j <= sum;j++) {
			dp[j] = min(dp[j], dp[j - arr[i]] + 1);
		}
	}

	if (dp[sum] == 100001) cout << -1 << endl;
	else {
		cout << dp[sum];
	}

	return 0;
}

 

이런 유형에서는 아래와 같은 패턴이 나오는데

	for (int i = 1;i <= n;i++) {
		for (int j = arr[i];j <= sum;j++) {
			dp[j] = min(dp[j], dp[j - arr[i]] + 1);
		}
	}

아래 그림을 보면 조금 이해가 갈거다.

밑에 3개의 줄은 각각 동전이 1원만 있을때 , 5원이 추가 됐을때 , 12원이 추가 됐을때다.

이렇게 추가 될때마다 원하는 합계를 만들기 위한 동전의 갯수가 달라진다.

이때가 핵심인데 dp[j]=min(dp[j] , dp[j-arr[i]]+1);

이라는 코드에서 dp[j-arr[i]]+1 여기서 빼는 arr[i]가 주어지는 동전이다.

위에서 for 문이 돌면서 j=arr[i] 부터 sum 까지 도는데 

이건 arr[i]가 5원동전이라면 5원 동전이 추가되고 생기는 변화(dp[5] 이상부터 변화가 생길거다. 왜? 그전에는 어짜피 5원을 쓰지도 못하니까)를 dp[sum]까지 업데이트 해주는거다.

 

똑같이 12원이 추가되는 차례에서도 똑같다. 

실제로 위의 표를 봐도 그렇게 변화가 업데이트 된다.

 

동전2 문제는 동전 조건이 추가되는거라서 - arr[i] 를 해주는거다. 그러니까 예를 들면 d[13](13원을 만들때의 최소 동전수) 를 구하고 싶은데 12원 동전이 추가되기전 그러니까 1동전과 5동전만 있을때는 5개가 필요했는데.

12원짜리 동전이 추가되면 dp[13-12]+1 -> 13원에서 13원중에서 12원을 동전하나로 채우니까 +1 을 해주는거고    dp[13-12] = dp[1]은 1원을 채우기 위한 동전 갯수가 되는거다. 그래서 결국 2개의 동전으로 된다는 뜻

이렇게 반복하면 원하는 합을 구하기 위한 최소 동전갯수를 구할 수 있게 되는 것.

 

 

제곱수의 합도 똑같다.

 

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j*j <= i; j++){
            if (Dp[i] > Dp[i - j*j] + 1 || Dp[i] == 0)
                Dp[i] = Dp[i - j*j] + 1;
        }
    }

 

코드가 좀 다르게 적혀있을뿐 위에서 min 해준거랑 독같다.

여기선 dp[i- j*j] 인데 이때는 동전대신 -j*j 이다. 

왜그렇냐? 동전은 숫자가 정해져서 들어와서 배열에 있는걸 가져와서 뺀거고

이건 제곱수가 순서대로 들어오는거니까 이렇게 제곱수를 빼주는거다. 

그럼 예를 들어보자. 

dp[10]을 구하고 싶다. dp[10-3*3]+1 은 결국 3^2 + 1^2 을 표현한거랑 같다. 

 

위 동전 문제처럼 3^2가 항의 갯수를 1 차지하므로 1을 더해준거다