백준 1431번 "1로 만들기" [Dynamic Programming 알고리즘]

문제

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std; 


int main()
{
	int Number;
	
	cin >> Number; 
	vector<int> m_vec(Number+1, 1000000);
	m_vec[1] = 0; 

	for(int i=2; i<=Number; i++)
	{
		m_vec[i] = m_vec[i - 1] + 1;

		if (i % 2 == 0)
			m_vec[i] = min(m_vec[i], m_vec[i / 2] + 1);
		if (i % 3 == 0)
			m_vec[i] = min(m_vec[i], m_vec[i / 3] + 1);
	}

	cout << m_vec[Number];
	

	return 0; 
}

 

 

문제 풀이 순서 

 

1. 처음에는 DFS 알고리즘을 고민했다. 그러나 이 방법은 지수 복잡도를 가지므로 가장 큰 수가 10^6이므로 지수복잡도를 가지는      DFS로 3가지 방향으로 간다면 시간초과 오류가 발생할 것이라 생각해서 PASS 했다. 

 

2. 그렇다면 생각을 바꿔 Dynamic Programming 알고리즘을 사용해봐야 겠다고 생각했다. ( 메모리를 재사용하는 알고리즘 )

    왜냐하면,  문제에서 준 예시가 10->9->3->1 이라면  각각 1,3,9,10의 연산횟수를 저장해 놨다가 사용한다면 

    시간복잡도는 O(N)이 되기 때문이다. 

 

    좀 더 자세히 설명해서 처음 1은 연산횟수가 0이다 

     -   (1) 다음 1*2 은 결과값이 2 이고 연산횟수가 2이고

     -   (2) 다음 1*3 은 결과값이 3 이고 연산횟수가 2이고 

     -   (3) 다음 1+1 은 결과값이 2 이고 연산횟수가 2이다. 

 

 

   이렇게 나누지말고 거꾸로 생각해보면 각각의 수의 연산횟수를 백터의 인덱스와 매칭시켜서 저장해놓으면 

   해당 값을 구할때 이미 그 인덱스 안에는 최소 경우의 수가 적혀져 있다는 생각을 해봤다. 

  

 

3. 마무리로 해당 인덱스를 Console out 해줘서 문제를 풀어보았다.