210124 | 백준 1463 | C++

1463번 : 1로 만들기

🎈 문제 풀이

우선, 각 숫자마다 필요한 연산횟수를 저장한 arr를 만들어준다. 인덱스 1부터 순서대로 올라가며 각 상황에서 최소횟수를 판단하여 arr에 저장하는 것이다. 그림을 그리며 이해하면 더 쉽다!

역으로 각 경우를 생각하여 algorithm 헤더의 min함수를 사용하여 판단하는 것이다.

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

int arr[1000000];

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

	arr[1] = 0;
	
	for (int i = 2; i <= N; i++) {
		arr[i] = arr[i - 1] + 1;
		if (i % 3 == 0)
			arr[i] = min(arr[i / 3] + 1, arr[i]);
		if (i % 2 == 0)
			arr[i] = min(arr[i / 2] + 1, arr[i]);

	}
	cout << arr[N];
}