개요

[링크]백준 1463번: 1로 만들기

• 입력
  첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

• 출력
  첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

접근 방식

• 첫 번째 방법
  바텀-업 방식으로 i가 3으로 나눠 떨어질 시,
  dp[i]= max( dp[i/3]+1, dp[i-1]+1)
  i가 2로 나눠떨어질 시,
  dp[i]= max( dp[i/2]+1, dp[i-1]+1)
  이런 식으로 채워 나가는 방법이다.

• 두 번째 방법
  마찬가지로 바텀-업 방식이지만
  각 i에 대해서 2나 3으로 나눠보는 방식이 아니라,
  2나 3을 곱한값을 미리 dp배열에 저장하는 방식이다.

  dp[i+1] = min(dp[i+1], dp[i] + 1);
  if (i*2 <MAX) dp[i*2] =min( dp[i*2], dp[i]+1);
  if (i* 3<MAX) dp[i*3] =min( dp[i*3], dp[i]+1);
  이런 식으로 곱한값을 배열에 저장하고 각 i에서 비교한 후
  다시 곱해서 저장하고 반복하는 방식이다.

• 세 번째 방법
  탑-다운 방식으로
  dp배열에 다 -1값을 넣어 놓고
  매 재귀마다 dp 원소값이 -1이 아니라면
  해당 값 return하는 식으로 return조건을 세웠다.

첫번째 방식 코드

#include<iostream>
#include<vector>
using namespace std;
const int MAX = 10'000'000;

vector<int> dp(MAX,MAX);

//입력받는 함수
void input(int& amount) {
	cin >> amount;
}
//바텀 업 방식으로 배열을 채워넣기(O(N)의 시간복잡도/ 범위가 최대 10^6이라서 가능)
void solution(int& amount) {
	dp[0] = 0;
	dp[1] = 0;
	for (int i = 2; i <= amount; i++) {
		dp[i] = min(dp[i], dp[i - 1] + 1);
		//3으로 나눠 떨어질 시
		if (i % 3 == 0) dp[i] =min( dp[i / 3] + 1, dp[i]);
		//2로 나눠 떨어질 시
		if (i % 2 == 0) dp[i] =min( dp[i / 2] + 1,dp[i]);
	}
}

int main() {
	int amount = 0;
	input(amount);
	solution(amount);
	cout << dp[amount];
}

두번째 방식 코드

#include<iostream>
#include<vector>
using namespace std;
const int MAX = 10'000'000;

vector<int> dp(MAX,MAX);

//입력받는 함수
void input(int& amount) {
	cin >> amount;
}



//바텀 업 방식으로 배열을 채워넣기 2 (2나 3으로 나눠떨어질시 추가하는 방식이아니라 2랑 3을 곱해버린후 저장하고 나중에 비교)
void solution(int& amount) {
	dp[0] = 0;
	dp[1] = 0;
	for (int i = 1; i <= amount; i++) {
		//2나 3을 곱하고 저장하므로 1부터 시작, i+1값을 다룰수있는 이유는 2,3을 곱해서 저장했으므로 i+1값이 있을 수도 있음
		dp[i+1] = min(dp[i+1], dp[i] + 1);			
		//i값에 2를 곱한값이 범위를 넘지 않는다면 2곱한값이 저장된 값과 지금값+1값 비교
		if (i*2 <MAX) dp[i*2] =min( dp[i*2], dp[i]+1);
		//i값에 3를 곱한값이 범위를 넘지 않는다면 3곱한값이 저장된 값과 지금값+1값 비교
		if (i* 3<MAX) dp[i*3] =min( dp[i*3],dp[i]+1);
	}
}

int main() {
	int amount = 0;
	input(amount);
	solution(amount);
	cout << dp[amount];
}

세번째 방식 코드

#include<iostream>
#include<vector>
using namespace std;
const int MAX = 10'000'000;

vector<int> dp(MAX,MAX);

//입력받는 함수
void input(int& amount) {
	cin >> amount;
}


//탑다운 방식으로 구현 큰문제부터 쪼개나감
int solution(int amount) {
	if (amount == 1) return 0;
	if (dp[amount] != MAX) return dp[amount];

	int Ans = solution(amount - 1) + 1;


	if (amount % 3 == 0) Ans = min(Ans, solution(amount / 3) + 1);
	if (amount % 2 == 0) Ans = min(Ans, solution(amount / 2) + 1);
	dp[amount] = Ans;
	return Ans;

}

int main() {
	int amount = 0;
	input(amount);
	cout << solution(amount);
}

문풀후생

탑-다운 방식과 바텀-업 방식으로 풀어봤는데
아직 좀 개념이 머리에 안 박힌것 같다.
더 다양한 문제를 풀면서 익혀야겠다.