[C++] 백준 1463번 : 1로 만들기

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

1463번: 1로 만들기

---

문제 접근

 배열 DP는 연산횟수가 저장된 배열이다. 함수는 3으로 나누었을 때, 2로 나누었을 때, 1을 뺏을 때 세 가지 경우를 따졌을 때 가장 적은 연산횟수를 저장하고 반환한다.

느낀점

 처음 작성한 코드가 문제가 있었는데 생각보다 간단하게 이해가 되지 않았었다. 최초의 코드는 모든 경우를 따지지 않고 경우를 나누었기 때문에 최소 연산 횟수를 정확하게 반환하지 못했다.

int solution(int n) {
	if (n == 1 || n == 0) return 0;
	if (dp[n] == 0) {
		if (n % 3 == 0)	dp[n] = min(solution(n / 3) + 1, solution(n - 1) + 1);
		else if (n % 2 == 0) dp[n] = min(solution(n / 2) + 1, solution(n - 1) + 1);
		else dp[n] = solution(n - 1) + 1;
	}
	return dp[n];
}

 

 

코드

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

int n;
int dp[1000001] = { 0, 0, };

int solution(int n) {
	if (n == 1 || n == 0) return 0;
	if (dp[n] == 0) {
		dp[n] = solution(n - 1) + 1;
		if (n % 3 == 0) dp[n] = min(solution(n / 3) + 1, dp[n]);
		if (n % 2 == 0) dp[n] = min(solution(n / 2) + 1, dp[n]);
	}
	return dp[n];
}

int main() {
	cin >> n;
	cout << solution(n);
}