[백준 알고리즘 C/C++] 1463번 문제 풀이 : 1로 만들기

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 실버 4

백준 알고리즘 1018번 체스판 다시 칠하기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

---

● 풀이 방법

DP 알고리즘을 통해 해결할 수 있다!!

우리가 한 숫자에 대해 1로 만들기 위해 할 수 있는 행위는 총 3가지로 한정된다.

1. 1빼기

2. 2로 나누기

3. 3으로 나누기

일단 먼저 가장 기본적으로 1빼기 방식만 사용하게 될 경우

알아보고자 하는 값은 이전 값에서 연산횟수는 1회 추가가 된 값이다.

ex) 4을 1빼기 방식으로 1로 만들려면 "3을 1빼기 방식으로 1을 만들기 위해 수행한 연산"에 1회 추가로 연산이 필요하다.

그러나 여기서 2번계산법과 3번계산법이 있으니 위 방식대로만 진행하면 안되고 우린 또 다른 조건식을 설정해야 한다.

 

현재 구하고자 하는 값이

2로 나뉘어 진다면, 현재 구하는 값/2 에서 연산을 한번 더 추가하면 된다.

3로 나뉘어 진다면, 현재 구하는 값/3 에서 연산을 한번 더 추가하면 된다.

---

● 소스 코드

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

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int num, DP[1000000] = {0,};
	cin >> num;

	for (int i = 2; i <= num; i++) {
		DP[i] = DP[i - 1] + 1;

		if (i % 2 == 0) 
			DP[i] = min(DP[i], DP[i / 2] + 1);
		if (i % 3 == 0) 
			DP[i] = min(DP[i], DP[i / 3] + 1);
	}
	std::cout << DP[num];
	return 0;
}

 

시간제한이 빡빡하여 

ios_base::sync_with_stdio(0); 와 cin.tie(NULL);를 사용했다.

 

 

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무