[백준/C++/DP] 1463 1로 만들기

0. 풀이한 문제

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

 

1. 테스트 케이스 분석

계산할 수 있는 방법은 총 세 가지

- 3으로 나누어 떨어지면 3으로 나누기

- 2로 나누어 떨어지면 2로 나누기

- 1 빼기

 

예제로는 부족한 것 같아서 1부터 10까지 직접 계산해봤다

모눈 한 칸이 계산 한 번이고

각 숫자마다 계산은 아래 방향으로 진행되며

최하단은 계산 횟수를 기록했다

 

이 문제를 단순하게 나눌 수 있는 숫자로만 생각한다면

10은 2로 5번 나눌 수 있기 때문에

결과로 출력되어야 하는 최단 횟수 3과 다르다

 

여기서 주의해야할 점을 알 수 있는데

10을 계산할 때 2로 나누어진다고 하더라도 

1을 빼는 방법으로 (ex. 10-1=9)

이전 차례에 계산해두었던 가까운 숫자들의 계산 횟수를 이용하는 것이다

 

비슷한 상황으로는 5와 7이 있다 

이 숫자들은 10과 달리 2와 3으로 나눌 수는 없지만

1을 빼서 2 또는 3으로 나눌 수 있는 숫자로 바꾼 후 계산할 수 있다

 

 

규칙을 찾아보면 

 

동적 프로그래밍 방식으로 풀이할 수 있다

 

 

3으로 나누어 떨어지는 경우

3으로 나눈 후 갱신된 결과값 차례에서  i/3

이미 계산된 횟수에 dp[i/3]

방금 나눈 횟수 1회를 더한다 +1

 

2로 나누어 떨어지는 경우

2로 나눈 후 갱신된 결과값 차례에서  i/2

이미 계산된 횟수에 dp[i/2]

방금 나눈 횟수 1회를 더한다 +1

2와 3으로 나누지 않고 1을 빼기로 한 경우

1을 뺀 후  i-1

1 작은 숫자 차례에서

이미 계산된 횟수에 dp[i-1]

방금 뺀 것 횟수 더하기 +1

 

2. 코드

#include<iostream>
#include<algorithm>
using namespace std;
int main(){    
	int N;    
	cin >> N;
	int dp[10000001];
  dp[0] = 0;    
  dp[1] = 0;    
  dp[2] = 1;    
  dp[3] = 1;
  for(int i=4; i<=N; 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);      
	}    
	cout << dp[N];    
	return 0;
}