[백준/C++] 1463번_1로 만들기

드디어 DP 시작입니다.
문제는 다음과 같습니다.

어떤 수 n이 주어졌을 때,
마지막 연산이 될 수 있는 경우의 수는 3가지입니다.

1. 1을 뺀 경우
2. 2로 나눈 경우
3. 3으로 나눈 경우

그리고 이 세 가지 경우 중 최소값이 구하는 답이 될 것입니다.

어떤 수 n을 1로 만드는 연산의 최소 횟수를 배열 a[n]에 담는다고 하면,

먼저, a[1]=0 이고
a[2]=1, a[3]=1 입니다.

그리고 점화식은 다음과 같습니다.

a[n]=a[n-1]+1 // 마지막 연산의 결과가 1을 뺀 경우

if(n%2==0) a[n]=min(a[n], a[n/2]+1); // 마지막 연산의 결과가 2로 나눈 경우
if(n%3==0) a[n]=min(a[n], a[n/3]+1); // 마지막 연산의 결과가 3으로 나눈 경우

각각의 경우에 해당되었을 때를 모두 구하고, 그 중에서 minimum값이 구하는 n에 대한 a[n]의 결과입니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a[1000001]={0, };
    int n;
    cin>>n;

    for(int i=2; i<=n; i++){
      a[i] = a[i-1]+1;
      if(i%2 == 0) a[i]=min(a[i], a[i/2]+1);
      if(i%3 == 0) a[i]=min(a[i], a[i/3]+1);
    }
    
    cout<<a[n]<<endl;
    return 0;
}

이 문제에서 가장 중요하다고 느낀 것:

🔥무조건 3으로 나누는 것이 최소 횟수가 아니라는 것!!🔥

-> 따라서 수행할 수 있는 세 가지 경우의 수 중 최소값을 구해주어야 한다.

---

복습 풀이)

진짜 무조건 복습을 해야함을 더 절실히 느낀다.
양치기 좋아하는데 ㅠㅠ 아무튼 나는 단기기억력 동물이기에 ,, 복습 그리고 기록만이 살길이다
진짜 보고 풀었던 기억도 가물가물했다.🥺

2/5 토요일 복습

첫 복습 풀이로는 bottom-up 방식을 이용하였다.

1. Bottom-up 방식

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int dp[1000001];
    fill_n(dp, 1000000, 1000000);
    int n; cin>>n;

    dp[1]=0; // 초기세팅

    for(int i=2; i<=n; i++){
      if(i%3==0) dp[i]=dp[i/3]+1;
      if(i%2==0) dp[i]=min(dp[i], dp[i/2]+1);
      dp[i]=min(dp[i], dp[i-1]+1);
    }

    cout<<dp[n]<<endl;
    return 0;
}

<개선 + 최적화>

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int dp[1000001]={0, };
    int n; cin>>n;

    for(int i=2; i<=n; i++){
      dp[i]=dp[i-1]+1;
      if(i%3==0) dp[i]=min(dp[i], dp[i/3]+1);
      if(i%2==0) dp[i]=min(dp[i], dp[i/2]+1);
    }

    cout<<dp[n]<<endl;
    return 0;
}

최소값을 구하려고 이 전에서는 배열을 초기화를 진행하였는데,
이를 없애고,
반복문에서 세 가지 경우에 대해 비교하는 것의 순서를 바꿔주어
(1을 빼주는 것을 먼저 시작)
최소값을 구하는 것에 있어 코드를 개선시켰다.

그리고 복습에서는 top-down을 이용해서도 풀어보았다.

2. Top-down 방식

#include <bits/stdc++.h>
using namespace std;

int dp[1000001]={0, };

int func(int k){
  if(k==1) return 0;
  if(dp[k]) return dp[k];
  else{
    dp[k]=func(k-1)+1;
    if(k%3==0) dp[k]=min(dp[k], func(k/3)+1);
    if(k%2==0) dp[k]=min(dp[k], func(k/2)+1);
    return dp[k];
  }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin>>n;

    cout<<func(n)<<endl;
    return 0;
}

확인해보았는데,
이 풀이에서는 bottom-up이 훠어어어얼씬 더 효율적이었다.😊