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

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

1463번: 1로 만들기

 

---

 

정수 N을 1로 만들기 위해서 사용할 수 있는 연산은 다음 세 가지이다. 편의상 연산 A, B, C라고 하겠다

 

연산A	N이 3으로 나누어 떨어지면, 3으로 나눈다.
연산B	N이 2로 나누어 떨어지면, 2로 나눈다.
연산C	1을 뺀다.

 

 

---

 

정수 N이 2인 경우

 연산A: 불가능하다

 연산B: 2 / 1 = 1이므로 1이 만들어진다. (연산횟수:1)

 연산C: 2 - 1 = 1이므로 1이 만들어진다. (연산횟수:1)

 

 최소 연산 횟수는 1이다.

---

정수 N이 3인 경우

 연산A: 3 / 1 = 1이므로 1이 만들어진다. (연산횟수:1)

 연산B: 불가능하다

 연산C: 3 - 1 = 2 이다. 2를 1로 만드는 최소연산을 또다시 수행해야 하는데, 위에서 이미 했다. (연산횟수:1+1=2)

 

 최소 연산 횟수는  1이다.

---

정수 N이 4인 경우

 연산A: 불가능하다

 연산B: 4 / 2 = 2이다. 2를 1로 만드는 최소연산을 또다시 수행해야 하는데, 위에서 이미 했다. (연산횟수:1+1=2)

 연산C: 4 - 1 = 3이다. 3을 1로 만드는 최소연산을 또다시 수행해야 하는데, 위에서 이미 했다. (연산횟수:1+1=2)

 

 최소 연산 횟수는 2다.

---

정수 N이 5인 경우

 연산A: 불가능하다

 연산B: 불가능하다

 연산C: 5 - 1 = 4이다. 4를 1로 만드는 최소연산을 또다시 수행해야 하는데, 위에서 이미 했다. (연산횟수:1+2=3)

 

 최소 연산 횟수는 3이다.

---

정수 N이 6인 경우

  연산A: 6 / 3 = 2이다. 2를 1로 만드는 최소연산을 또다시 수행해야 하는데, 위에서 이미 했다. (연산횟수:1+1=2)

  연산B: 6 / 2 = 3이다. 3을 1로 만드는 최소연산을 또다시 수행해야 하는데, 위에서 이미 했다. (연산횟수:1+1=2)

  연산C: 6 - 1 = 5이다. 5를 1로 만드는 최소연산을 또다시 수행해야 하는데, 위에서 이미 했다. (연산횟수:1+3=4)

---

정리하면,

 연산을 수행할 수 있는 경우,

    연산 결과값이 1이라면, 연산 횟수 = 1

    연산 결과값이 1이 아니라면, 연산 횟수 = 1 + 결과값의 최소 연산 횟수

 

 연산 횟수 중 최소값이 정답이다.

 

 따라서 2부터 N까지의 최소 연산 횟수를 배열에 모두 저장해 두었다가, 필요한 경우 그 값을 가져와서 사용하면 되겠다. 

 

 

---

 

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

int main(){
	
	vector<int> DP={0,0,1,1};
	
	int n; cin >> n;

	for(int i=4;i<n+1;i++) {
		int result = DP[i-1]+1;
		if(i%3==0) result= min(result,DP[i/3]+1);
		if(i%2==0) result = min(result,DP[i/2]+1);
		DP.push_back(result);
		}
		
	cout<<DP[n];
	return 0;
}

 

DP[0], DP[1]은 안쓸거니까 0으로 초기화

DP[2], DP[3]은 어차피 1인거 알고있으니 1로 초기화해주고 시작했다

 

연산C는 정수 N의 값에 관계 없이 항상 수행 가능하다

따라서 DP[N]에 연산C 결과를 우선 저장하고,

연산 A와 B가 가능하다면 그 결과값이 DP[N]보다 작은 경우에만 DP[N]으로 갱신해주었다.

 

---