[알고리즘] 백준 알고리즘 1463 1로만들기 DP - 시간복잡도 분석

안녕하세요, 감자코딩에 감자개발자입니다.

제가 이번에 포스팅할 내용은 DP의 대표적인 문제인 1로만들기 문제인데요.

이번에 복습겸 다시 공부를 하게 되면서 시간복잡도 부분에 대해서 조금 더 포스팅 해보려고해요. 전에 Bottom-up 방식과 Top-Down방식으로 매우 세세하게 포스팅하였지만, 시간복잡도 부분에 대해서는 제가 설명을 제대로 하지 못한 부분이 있었다고 판단이 들어 추가 포스팅을 하겠습니다.

전에 올렸던 포스팅입니다. 처음이신분들은 한번 보시고 오시면 도움이 되실겁니다.

---

[알고리즘] 백준 알고리즘 1463 1로 만들기(Top-Down/Bottom-Up, 피보나치수열) C++

https://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0ButtomUp%EB%B0%A9%EC%8B%9D

---

1. 문제

문제링크 

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

---

1로 만들기 성공

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초 128 MB 58921 19143 12340 32.115%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.

X가 2로 나누어 떨어지면, 2로 나눈다.

1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

2. 시간복잡도 분석

 

차근 차근 문제 접근방법에 대해서 알아보겠습니다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.

X가 2로 나누어 떨어지면, 2로 나눈다.

1을 뺀다.

이 세가지 조건이 여기 문제에서 가장 중요한 힌트인데요. 여기서 하나의 낚시가 있습니다.

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 이 경우를 살펴보죠.

원래 기존같았으면 10에다가 2를 나누면 5가되고 5에서 -1을 뺀 값은 4가 되고 2로 두번나누게 되면 1이 나오게됩니다.

10 -> 5 -> 4 -> 2 -> 1 (총 5번의 연산횟수) 라고 생각하실겁니다 대부분은

하지만, 맨처음에 -1을 빼서 

10->9->3->1로 만드는 총 4번의 연산횟수가 나오는것을 확인 하실 수 있습니다.

이것만 주의 하시고, 밑에 차근차근한 설명을 해드리겠습니다.

 1) N/3

 N개에서 1까지의 연산에 따라 최소 횟수를 구해야합니다.

 따라서 N개에서 N/3 으로 가는 연산의 횟수는 1

 N/3 에서 -> 1로 가는 연산의 횟수는 N/3

 총 연산의 횟수는 N/3 + 1

 

 2) N/2

 N개에서 N/2 으로 가는 연산의 횟수는 1

 N/2 에서 -> 1로 가는 연산의 횟수는 N/2

 총 연산의 횟수는 N/2 + 1

 

 3) N-1

 N개에서 N-1 으로 가는 연산의 횟수는 1

 N-1에서 -> 1로 가는 연산의 횟수는 N-1

 총 연산의 횟수는 N-1 + 1

 1), 2), 3) 의 총 연산의 횟수

 

 4) 메모이제이션

 이제 이렇게 연산을 해야한다는 것을 알았으니 우리가 DP값을 이용하여

 반환을 어떻게 받을지 생각해야합니다.

 DP에 있는 값이 > 0 보다 클 경우에 값이 있는것이므로 그 데이터만 반환 시켜줘야합니다.

 메모이제이션으로 불필요한 메모리 낭비를 막기 위함 입니다.

 그러면, return 값으로 dp[n]값으로 해주면 됩니다.

 

 5) 재귀호출을 종료시키기 위한 조건

1을 이미 구했기  약 들어온 N의 값이 1일 경우에는 프로그램을 종료 시킵니다. 

 

 6) 시간복잡도

 

 1),2),3)에서 설명한것과 같이 N에서 N/3, N/2, N-1 로 가는 복잡도는 각각 1씩이다

 총 3인경우인데, 이것은 O(1)로 시간복잡도를 표현 할 수 있습니다.

 그리고, 전체데이터의 개수는 N개 만큼이므로 O(N)의 시간복잡도가 걸립니다.

 

 여기서 보면 10^6의 경우 1,000,000 백만까지의 시간복잡도를 가지게 되므로

 O(N)+O(1)의 복잡도가 성립하는것을 알 수 있습니다.

 

 만약 O(N^2)의 시간복잡도가 나타나게 될 경우 O(1,000,000^2)가 되어

 1,000,000,000,000 1조의 시간복잡도가 나타나는것을 알 수 있습니다.

결국 O(N) + O(1) 만큼의 시간복잡도가 문제의 시간복잡도에 맞게 문제를 해결하게 되었습니다.

3. 소스코드

#include <stdio.h>

#include <iostream>

using namespace std;

int dp[1000001];

int recursive(int n){

    

    // 1이 완성된 경우

    if(n == 1){

        return 1;

    }

    // 값 있을 경우

    if(dp[n] > 0){

        // 메모이제이션

        return dp[n];

    }

    // -1의 경우는 따로 조건이 없으므로 바로 계산.

    dp[n] = dp[n-1] + 1;

    // n/3

    if(n % 3 ==0){

        // 최소 값이 있을 경우 Swap

        int temp = dp[n/3] + 1;

        if(dp[n] > temp){

            dp[n] = temp;

        }

    }

    // n/2

    if(n % 2 == 0){

        // 최소 값이 있을 경우 Swap

        int temp = dp[n/2] + 1;

        if(dp[n] > temp){

            dp[n] = temp;

        }

    }

    return dp[n];

}

int main(void){

    int n;

    cin >> n;

    int result = recursive(n);

    cout << result;

    

    return 0;

}

이렇게 시간복잡도 분석에 대한 고민을 한번 더 해보면서 복습을 하게 되었습니다.

궁금하신 사항이나 제가 잘못된 부분이 있으면 피드백 주시면 감사하겠습니다.

이상 감자코딩에 감자개발자였습니다.