알고리즘 #13 (DP, 백준 1463번, 11726번) [C++]

DP 3번째

 

[백준 1463번]

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

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>

using namespace std;

int DP[1000001];

void minCount(int N) {
	for (int i = 2; i <= N; i++) {
		DP[i] = 1 + DP[i - 1];
		if (i % 2 == 0) DP[i] = min(1 + DP[i / 2], DP[i]);
		if (i % 3 == 0) DP[i] = min(1 + DP[i / 3], DP[i]);
	}
	cout << DP[N];
}

int main() {
	int N;
	cin >> N;
    minCount(N);
}

이전 문제를 풀어봐서 그런지 생각보다 수월하게 풀렸다.

전에 DP문제 풀어보려고 했을 때 첫 문제가 이 문제였는데 모르겠어서 좌절했던 문제인데 풀리니까 완전 뿌듯하다!!!

아주 살짝 DP 감을 잡은듯..?

 

원래는 위의 DP 배열을 지역변수로, 이름은 count로 선언했었는데 배열 크기가 때문에 에러가 발생해서 전역으로 내보냈다. 전역으로 선언한 이후에도 count라는 이름이 std에 함수 중에 겹치는게? 있는지 "count가 모호합니다" 에러가 발생했다. 그래서 사람들이 DP문제에서 배열 이름으로 DP를 많이 쓰길래 따라했다.

 

[백준 11726번]

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

11726번: 2×n 타일링

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    
    int DP[1001] = {0, 1, 2, };
    
    for(int i=3; i<=n; i++)
        DP[i] = (DP[i-1] + DP[i-2]) % 10007;
    
    cout << DP[n];
}

이 문제는 규칙 찾는 것은 매우 쉬웠다.

DP문제들은 n이 1, 2, 3 ... 일 때의 경우의 수를 각각 손으로 적다보면 규칙 찾기가 수월한 것 같다.

 

그렇게 찾은 규칙이 DP[i] = DP[i-1] + DP[i-2] 인데, 

처음에는 경우의 수를 모두 구한다음 출력할 때만 10007로 나머지를 구했다.

그러다보니 n이 1000으로 갈수록 수가 너무 커져 unsigned long long으로도 감당이 안되고 잘못된 값이 나왔다. 

생각해보니까 수를 완전히 구할 필요 없이 각각의 나머지들만 더하고 10007로 나머지를 구해도 똑같은데...^^

n-2 → 10007*x1 + d1,

n-1 → 10007*x2 + d2 일 때

n → 10007*x1 + d1 + 10007*x2 + d2 = 10007*(x1 + x2) + (d1 + d2) 이니 말이다...

참 간단한건데도 생각해내는데는 난 아직 연습이 필요한 것 같다.