[BOJ/백준 1463][C++] 1로 만들기

문제

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

 

문제 내용

할 수 있는 연산은 3가지이다.

3으로 나누거나, 2로 나누거나, 1을 빼는 것

위 3가지 연산을 최소한으로 사용해서 입력받은 수를 1로 만들면 된다.

 

문제 풀이

문제를 보면 dynamic programming이라는 것은 짐작이 올 것이다.

dp이긴 한데 조건을 어떻게 새워야 할까?

2나 3으로 나누어 떨어지면 그냥 나누는 것을 선택하는게 좋을까?  => 아니다

문제에서 준 힌트를 보니 10의 경우 10 -> 9 -> 3 -> 1의 순서가 가장 연산이 적다고 되어있었다.

10의 경우 2로 나누어 떨어지지만, 1을 먼저 뺀 경우가 더 연산 숫자가 적다.

 

이를 적용해보자면, 

1) 2 또는 3으로 나누어지지 않는다 => 1을 뺀다.

2) 2로 나누어진다. => 1을 뺀 것과 2로 나누는 것 중에 연산이 적은 것을 고른다.

3) 3으로 나누어진다. => 1을 뺀 것과 3으로 나누는 것 중에 연산이 적은 것을 고른다.

 

코드

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

//실패

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n;
	cin >> n ; // 1~10^6
	vector<int>dp(n+1,0);
	
    	//문제 해결
	dp[1] = 0; //연산 필요 없음
	dp[2] = 1;
	dp[3] = 1;
	
	for (int i = 4; i < n + 1; 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]<< '\n';

}

 

문제 코드 설명

1) 문제 해결

반복문을 돌리면 dp의 값을 계속 구해나가면 된다.

조건은 위에서 설명한대로 구현하면 된다.