백준 - 1로 만들기

dp 문제였다.

 

먼저 코드는 아래와 같다.

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

int dp[1000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;

	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;

	for (int i = 4;i <= n;i++) {
		dp[i] = dp[i - 1] + 1;

		if (i % 3 == 0) {
			dp[i] = min( dp[i / 3] + 1 , dp[i]);
		}
		if (i % 2 == 0) {
			dp[i] = min(dp[i / 2] + 1,dp[i]);
		}
	}

	cout << dp[n];
	


}

 

 

코드를 설명하자면 dp배열은 배열의 인덱스가 1이되는 최소의 횟수를 담는 배열이다.

그러니까 for 문이 작동하면서 숫자가 하나씩 늘어 최종적으로 dp[n]의 값을 구하게 되는데

 

1을 빼거나 , 3으로 나누거나 ,2로 나누는 선택지가 있으므로

인덱스가 증가할때마다 모든 경우를 다 실행해보고 거기서 가장 작은 횟수가 된 값을 dp에 저장한다.

dp[i/3]+1 처럼 계산하는 이유는 만약 i가 6이라면 3으로 나눴을때 

그러니까 숫자가 2일때의 최소횟수에서 계산횟수가 하나(3으로 나누는 방법) 증가한 것과 같기 때문이다.