[BOJ/C++]1463번 1로 만들기

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

1463번: 1로 만들기

알고리즘 수업시간에도 이해 못하고 시험 망쳤던 DP이해하는데 한 세월 걸렸던 문제.

추후에 알고리즘 복습하며 DP개념 정리하여 올릴것.

 

문제

사용자로부터 숫자 X를 입력받음. 이 n이 다음 세가지 조건에 따라 1이 되는 최소횟수를 구하는 문제

1. X%3==0 이면 3으로 나눈다- ex)9->3
2. X%2==0 이면 2로 나눈다- ex)4->2
3. 1을 뺀다- ex)5->4

 

풀이방식

사용자로부터 n을 입력받아 index가 n까지 있는, 즉 n+1짜리 배열을 만든다.

i번째 배열은 숫자 i가 1이 되는 최소의 숫자가 들어간다. 따라서 배열 dp[1]=0이다(1은 1까지 가는데 0번이 걸리므로). 

DP의 Bottom-up방식으로 i가 2부터 n까지 반복한다.

 

먼저 아무 조건 없이 수행 가능한 "조건3: 1을 뺀다"를 수행한다.

dp[i]=dp[i-1]+1;//규칙 3(1을 뺀다)

반복문을 한 번 수행하고 나면 무조건 dp배열에 1까지 가는 최소값이 저장된다. 그러므로 dp[i-1]은 i-1번째의 숫자가 1까지 가는 최소값 이므로 dp[i-1]+1을 하면 그 전 숫자에서 조건 3을 수행한 횟수가 dp[i]에 저장된다.

조건 3 수행 예시

 

 

그리고 i가 2로 나누어 떨어지는 "조건2: 2로 나눈다"와 조건 3을 비교해서 더 작은것을 dp[i]에 저장한다.

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

 여기서 먼저 dp[i]에는 앞서 수행한 조건3이 저장되어 있다. 조건 3과 조건 2인 dp[i/2]+1을 비교해서 더 작은 것을 dp[i]에 새로 저장한다. 여기서 min은 #include<algorithm> 라이브러리에 있다.

 아래는 조건 2를 수행하는 예시이다

조건 2 수행 예시

 

 

마지막으로 "조건 1: 3으로 나눈다"와 앞서 조건 2와 조건 3을 수행한 것 중 작은 것을 비교한다.

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

조건 1 수행 예시

소스코드

#include<iostream>
#include<algorithm>//min들어있는 라이브러리
using namespace std;

int main(void){
    int n;
    cin>>n;
    int dp[n+1];//우리의 목표: dp[n]에 저장되어있는 수(연산 3개로 1을 만드는 것)
    
    //bottom-up 방식으로 i가 1부터 n까지 올라감
    int i=2; dp[1]=0;//i=1일때는 0번째로 1에 도달할 수 있음.
    while(i!=n+1){
        dp[i]=dp[i-1]+1;//규칙 3(1을 뺀다)
        if(i%2==0)
            dp[i]=min(dp[i],dp[i/2]+1);//규칙 2(2로 나누어 떨어지면 2로 나눈다)->규칙 3과 규칙2중 작은거 적용시킴.
        if(i%3==0)
            dp[i]=min(dp[i],dp[i/3]+1);//규칙 3(3으로 나누어 떨어지면 3으로 나눔)->규칙 3,2,1중 작은거 적용
        i++;
    }
    cout<<dp[n]<<endl;
}