[BAEKJOON] 1463번 1로 나누기

오류 코드

#include <iostream> #include <fstream> #include <algorithm> #include <vector> using namespace std; vector<int> cache; #define INT_MAX 2147483647 int cal(int remain, int result) { if (remain == 1) return result-1; int &ret = cache[remain]; if (ret != INT_MAX) return ret; if (remain % 3 == 0) ret = min(ret, cal(remain / 3, result + 1)); if (remain % 2 == 0) ret = min(ret, cal(remain / 2, result + 1)); ret = min(ret, cal(remain - 1, result + 1)); return ret; } int main() { ifstream fcin; fcin.open("1463_input.txt"); int input; fcin >> input; cache = vector<int>(input + 1, INT_MAX); cout << cal(input, 0) << endl; for (int j = 0; j <= input; j++) cout << cache[j] << " "; cout << endl; system("pause"); }

정답 코드

#include <iostream> #include <fstream> #include <algorithm> #include <vector> using namespace std; vector<int> cache; #define INT_MAX 2147483647 int cal(int remain) { if (remain == 1) return 0; int &ret = cache[remain]; if (ret != INT_MAX) return ret; if (remain % 3 == 0) ret = min(ret, cal(remain / 3)+1); if (remain % 2 == 0) ret = min(ret, cal(remain / 2)+1); ret = min(ret, cal(remain - 1)+1); return ret; } int main() { int input=20; // cin >> input; cache = vector<int>(input + 1, INT_MAX); cout << cal(input) << endl; for (int j = 0; j <= input; j++) cout << cache[j] << " "; cout << endl; system("pause"); }

오류가 있는 코드가 내가 짠 코드이다.

그리고 밑이 정답 코드이다.

이 문제를 처음 봤을 때 처음 든 생각은

DP를 써야겠구나 였다

DP의 가장 중요한 것은 memorization이다. 어떻게 저장할 cache를 만들까?

1차배열을 만들었다. 1차배열에서 가장 큰 수 INT_MAX를 미리 저장해놓았다

왜냐하면 minimum을 저장해야하기 때문이다.

코드의 전체적인 흐름은 이렇다

나머지가 n일때 최소 값을 배열에 저장한다 그리고 그 다음으로 넘겨준다

이 과정을 반복하여 나타내는 것이다.

정답 코드는 가장 끝까지 간다 즉 remain이 1일때까지 간다 그리고 올라오면서 1을 더해주는 과정이다

나는 가장 끝까지 간다 하지만 내려가면서 더해준다. 그리고 올라오면서 결과 값을 return 해준다.

맨 처음 나도 정답코드 처럼 생각했다. 하지만 어떻게 구현할 지 방법을 몰랐다.

따라서 위에서부터 아래로 내려가면서 계속 더해주었고 결과값을 저장했다.

이것의 가장 큰 오류는 memorization이 제대로 되지 않는 다는 것이다.

만약 돌아가다가 ret!=INT_MAX이면 ret의 return해줘야하는데

remain이 남았을 때가 아닌 끝까지 돌아간 값을 return해준다.

나는 앞으로 배울 것이 너무 많다.

차근차근 알아가보자.