[1463] 1로 만들기

---

 

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

1463번: 1로 만들기

 

---

 

🔎 해결 방법

ucpc 캠프 2일차 '다이다믹 프로그래밍' 에서 제일 처음으로 풀었던 문제.

캠프 때 풀지 못해서 집에와서 다시 도전해보았는데 틀렸습니다 계속 떠서 접을 뻔...ㅎ

 

 내가 실수한 부분 

• c에서는 기본적으로 min, max함수를 제공하지 않기 때문에 반드시 매크로를 정의해주어야 한다.
  (예를 들어, #define min(a, b) (((a) < (b)) ? (a) : (b)) 와 같이!)
• 메인 함수에서 변수를 선언할 경우, 스택에서 메모리가 소모되는데 비쥬얼 스튜디오의 기본 스택 사이즈는 1MB밖에 되지 않아 큰 메모리를 사용할 경우에는 가급적 전역 변수로 선언해야 한다.
• '+1'은 연산을 이미 한 번 진행했다는 의미
• 점화식 : dp[n] = min(dp[n - 1], dp[n / 2], dp[n / 3]) + 1
• n이 2로 나누어 떨어지는지, 3으로 나누어 떨어지는지 확인하는 과정 필요, 이 때 if, else if가 아니라 if, if를 사용하여야 한다!        (ex. dp[6]은 2로도 나누어 떨어지고, 3으로도 나누어 떨어지기 때문에 두 과정 모두 거친 후에 더 작은 값으로 update 해야 함)

 

---

 

💡 내 코드

Ver.1(C++)

// [1463] 1로 만들기
// https://www.acmicpc.net/problem/1463
// dp

#include <iostream>
#define MAX 1000001
using namespace std;

int dp[MAX] = {0}; // 최소 연산 횟수

int main(void)
{
    int n;
    cin >> n;

    dp[0] = 0, dp[1] = 0;

    for(int i = 2 ; 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] << '\n';

    return 0;
}

 

Ver.2(C)

// [1463] 1로 만들기
// https://www.acmicpc.net/problem/1463
// Visual Studio's default stack size is 1MB, so if you allocate large memory, declare it as a global variable.
  
#include <stdio.h>
#define min(a, b) (((a) < (b)) ? (a) : (b))
int dp[1000001] = { 0 }; // The minimum number of operations to create as 1

int main(void)
{
    int n;
    scanf("%d", &n);
    dp[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        // '+1' = operation is performed once
        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);
    }
    
    printf("%d", dp[n]);
}

 

 

아직 다이나믹 프로그래밍이 뭔지.. 잘 감은 안오지만 열심히 해보자