(백준BAEKJOOB )- 1463번 -1로 만들기 "c++"

 

개인적으로 너무 어려웠다 dp에 익숙하지 않아서 그런지 모르겠지만 나한테 좀 많이 어려웠다.

문제를 풀기위해서는 dp알고리즘이 어떤 형식인지 알아야되고

 

문제에 있는 설명  3개를 이용하면 점화식 3개가 나오는데

dp[x/3]+1
dp[x/2]+1
dp[x-1]+1

이걸이용하여 풀도록 하겠다.

먼저 0부터 4까지 넣어보면 0 0 1 1이고 5부터는 값이 달라진다

 

그러면 

	d[0], d[1] = 0;
	d[2], d[3] = 1;

일단 적어주고 

 

그러면 i가 4부터 시작하는 반복문을 만들어주고 점화식을 이용해 값들을 넣어준다.

	for (int i = 4; i <= n; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);
		if (i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);
	}

min은 #include <algorithm>이걸 꼭 넣어줘야만 돌아간다.

ex>> min(1,2)  -> 작은 값을 반환해줌 

 

 

풀이를 봐도 이해가 안된다 .그래서 따로 cout을 다해봤다  10으로 예시를 들어보면

 

이런식으로 흘러가고 

i가 4일때만 한번 설명 해보겠다.

i가 4일때 d[4]=d[3]+1 결국 d[3]은 1이니까 d[4]의 값은 2가 나오고

i가 4일때 4%2==0 이성립이되니까 d[4]=min(d[4],d[2]+1) 더 작은값인 뒤에값 1을 출력

i가 4일때 4%3==0은 성립이 되지않기 때문에 넘어간다 

 

그럼 마지막까지 프로그램 되면 결국 a[10]은 3이라는 값이 나온다!

#include <iostream>
#include <algorithm>

using namespace std;

long d[1000001];

int main() {
    int n;
    cin >> n;

    d[0], d[1] = 0;
    d[2], d[3] = 1;

    for (int i = 4; i <= n; i++) {
        d[i] = d[i - 1] + 1;
        cout << "d[" << i << "] after first update: " << d[i] << endl;

        if (i % 2 == 0) {
            d[i] = min(d[i], d[i / 2] + 1);
            cout << "d[" << i << "] after second update: " << d[i] << endl;
        }

        if (i % 3 == 0) {
            d[i] = min(d[i], d[i / 3] + 1);
            cout << "d[" << i << "] after third update: " << d[i] << endl;
        }
    }

    cout << "Minimum number of operations to reach " << n << ": " << d[n] << endl;
    return 0;
}

코드를 이용하여 어떤식으로 만들어지는지 직접 해보자

 

 

 

총 코드

---

#include <iostream>
#include <algorithm>

using namespace std;



int d[1000001];
int main(){
	int n;
	cin >> n;

	d[0]=0,d[1] = 0;
	d[2]=1, d[3] = 1;


	for (int i = 4; i <= n; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 2==0) d[i] = min(d[i], d[i / 2] + 1);
		if (i % 3==0) d[i] = min(d[i], d[i / 3] + 1);
	}
	cout << d[n] << endl;
}