대엉코딩

www.acmicpc.net/problem/1463

1. 풀이방법

- 맨 처음에는 3으로 나누어떨어지면 -> 2로 나누어떨어지면 -> 이것마저 안되면 -1 이라고 생각했었는데

- 이럴경우 10->5->4->2->1  (답은 10->9->3->1)

- 그리고 나서 숫자를 쭉 써놓고 한번생각을 해보았는데

- 결국 비교해야 할 경우는 3가지 이다 N-1 과 N/3 과 N/2 이다.

- 중요한 것은 경우에 따라 N-1을 한 경우가 최소연산 일 수 있다는 것.

2. 주의사항

- 처음에는 항상 익숙한대로 탑다운 방식(재귀함수)를 이용했다.

-결과는 "메모리 초과"

- 문제 조건을 보았는데 메모리는 128MB까지 허용이 가능하고

- 내가 사용한 용량을 얼추 계산해봐도 1,000,000 * 4바이트(INT) 기껏해서 4MB 정도이다. (짜잘한 것은 생략.)

- 추측한 것은 재귀로 너무 깊이 들어가서 스택메모리가 초과되었나? 라는 생각

- 그래서 재귀를 사용하지 않고 바텀업 방식(반복문이용) 으로 짰더니 통과가 되었습니다.

3. 나의코드

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

int X;
int dp[1000001];

//메모리 초과
/*int getdp(int num) {
	if (dp[num] == 0) {
		if (num % 3 == 0) { dp[num] = min((getdp(num - 1) + 1), (getdp(num / 3) + 1)); return dp[num]; }
		else if (num % 2 == 0) { dp[num] = min((getdp(num - 1) + 1),(getdp(num / 2) + 1)); return dp[num]; }
		else { dp[num] = getdp(num - 1) + 1; return dp[num]; }
	}
	else { return dp[num]; }
}*/
void bottomup() {
	for (int i = 6; i < 1000001; i++) {
		if (i % 3 == 0) {dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);}
		else if(i%2==0){ dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1); }
		else { dp[i] = dp[i - 1] + 1; }
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> X;   //  X>1
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	bottomup();
	cout<<dp[X]<<"\n";
	return 0;
}

1. 다이나믹 프로그래밍 이란?

- Space(공간)을 더 사용하여 re-computing(중복되는 연산)을 방지하여 

  Speed(속도)를 증가시켜주는 방법입니다..

- solution 테이블을 사용하여 이미 연산된 적이 있다면 그 값은 바로 테이블에서 가져와서 쓰는 것입니다.

- 처음하는 연산의 경우 연산을 수행한 뒤 결과값을 solution table에 저장합니다.

- 일반적으로 최적해(Optimal Solution)을 구하는 데에 많이 사용된다.

2. Divide and Conquer(분할정복)과 차이점?

- 분할정복 역시 큰 문제를 작은 문제로 쪼개서 해결한다.

- 차이점은 DP에서는 부분(작은) 문제의 해가 중복되는 부분이 있어 나중에 또 필요하다는 것.

3.대표적인 예시

 (1) 피보나치 수열

     -피보나치 수열을 모든 연산을 반복적으로 수행하게끔 구현하면 n이 증가함에 따라

       총 연산의 수 가 급격히 높아진다.(중복되는 연산이 매우 많음)

-f(6)만 해도 이렇게 중복되는 연산이 많습니다.

- 빨간색은 연산없이 바로 테이블에서 끌어오는 녀석입니다.

(2) Matrix-Chain Multiplication 문제

- n개의 행렬이 주어졌을 떄 곱셈연산수를 가장 적게 하는 방법을 찾아라.

- (1~n)을 (1~k) * (k~n)으로 나누어야 하는데 어디를 나눌 것인가?

- 점화식과 관련이 깊다.

4. 해결절차

- (1) 최적해를 정의 한다.

- (2) 이를 바탕으로 점화식으로 표현한다

- (3) 바텀업방식이나 탑다운방식으로 이를 계산해 나간다.

5.구현방식

-(1) 바텀업 방식(Bottom-Up Approach)

     : 반복문 사용

       문제의 전체적인 구조를 파악하고 있어야 한다.

       재귀를 사용할 때의 오버헤드를 줄일 수 있다.

-(2) 탑다운 방식(Top-Down Approach)

     : 점화식의 구조를 직관적으로 파악하기 편하다.

       재귀함수 사용