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

문제출처: 백준 (baekjoon)
문제 링크: https://www.acmicpc.net/problem/1463
난이도: ★★☆☆☆

문제 분류: 다이나믹 프로그래밍(dp)

[문제]

 

---

[분석]

다이나믹 프로그래밍의 기본은 탑다운이 아닌, 바텀업(bottom up)이다.

따라서 문제에 해당하는 재귀식을 세운 뒤에 문제를 풀었다.

배열의 이름을 col 이라고 지었고 idx=0부터 차례대로 채웠다.

n=1 일 경우는 원래 1이기 때문에 연산을 하지 않으므로 연산 횟수가 0이고

n=2 or n=3 일 경우는 조건 1과 조건 2에 의해 연산 횟수가 1이 된다. 여기까지가 base case이다.

 

다음은 recursive case이다.

n이 3보다 클 경우, for문을 돌며 배열을 채워간다.

n=4일 경우, 조건 2와 조건 3만 만족하게 되는데,

4/2=2, 4-1=3이므로 col[2]와 col[3] 중 최소값을 구한 뒤, 그 값에 +1을 하였다.

나머지 수도 1부터 배열을 채워나간다.

10까지의 표는 다음같이 채울 수 있다.

[표]

n	1	2	3	4	5	6	7	8	9	10
연산횟수	0	1	1	2	col[4]+1=3	col[2]+1=col[3]+1=2	col[6]+1=3	col[4]+1=3	col[3]+1=2	col[9]+1=3
사용 조건	x	2	3	col[2]=1 col[3]=1	col[4]=2	col[2]=1 col[3]=1 col[5]=3	col[6]=2	col[4]=2 col[7]=3	col[3]=1 col[8]=3	col[5]=3 col[9]=2

[재귀식]

문제의 n의 범위가 10^6이므로 unsigned long long 으로 변수형을 선언해주었고

col[0]을 0으로 채워주었다.

---

[코드]

#include<iostream>
using namespace std;

unsigned long long col[1000001];



int main(){
	unsigned long long n;
	unsigned long long min_v;
	cin>>n;
	for(int i=1;i<=n;i++){
		if(i==1) col[i]=0;
		else if(i<4) col[i]=1;
		else
		{	
			min_v=col[i-1];
			if((i%3==0)&&(min_v>col[(unsigned long long)i/3])) min_v=col[(unsigned long long)i/3];
			if((i%2==0)&&(min_v>col[(unsigned long long)i/2])) min_v=col[(unsigned long long)i/2];
			col[i]=min_v+1;
		}

	}

	cout<<col[n]<<endl;
}