[C++] 백준 온라인 저지 1463번 1로 만들기 풀이

주어진 수를 1로 만드는 데 필요한 최소 연산 횟수를 구하는 문제

 

---

문제의 조건

 

1. 1보다 크거나 같고 10^6보다 작거나 같은 정수 N이 주어진다. 

 

2. 정수 N에 사용할 수 있는 연산은 3가지이다. 

1) 3으로 나누어 떨어지면 3으로 나눈다.

2) 2로 나누어 떨어지면 2로 나눈다.

3) 1을 뺀다.

 

3. 위 세 가지 연산을 적절히 사용할 때 주어진 N을 1로 만들 수 있는 최소 연산 횟수를 구해서 출력하기 

 

---

풀이 과정

 

아직 DP를 잘 몰라서 문제를 봐도 감이 잘 안 와서 풀이를 찾아봤습니다. 

 

여러 블로그를 보고 이해한 풀이 

 

1. DP 중에서 타뷸레이션(상향식 접근) 방식을 사용해 배열 인덱스에 해당 값을 1로 만드는 데 필요한 연산 횟수를 기록한다. 

각 숫자별로 필요한 연산 횟수를 기록할 1차원 배열이 필요하다. 

배열의 각 인덱스에 해당 숫자의 연산 횟수를 기록해야 하기 때문에 배열의 N번째 인덱스까지 접근이 가능해야 한다. 

그래서 N+1 크기의 배열이 필요하다. 

 

2. 연산 횟수를 저장한 배열을 DP라고 하면 

DP[N] 에는 N을 1로 만드는 데 필요한 연산 횟수를 저장한다. 

 

주어지는 N에 문제의 조건들을 적용하면

1) N을 3으로 나누면 N/3이 된다. 

반대로 생각하면 N/3에 3을 곱하면 N이 된다. 

N/3을 1로 만드는 데 필요했던 연산 횟수에 +1 하면 N을 1로 만들기 위한 최종 연산 횟수가 된다. 

 

2) N을 2로 나누면 N/2가 된다.

반대로 생각하면 N/2에 2를 곱하면 N이 된다.

N/2를 1로 만드는 데 필요했던 연산 횟수에 +1 하면 N을 1로 만들기 위한 최종 연산 횟수가 된다.

 

3) N에서 1을 빼면 N-1이 된다. 

반대로 생각하면 N-1에 1을 더하면 N이 된다.

N-1을 1로 만드는 데 필요했던 연산 횟수에 +1 하면 N을 1로 만들기 위한 최종 연산 횟수가 된다.

 

위의 아이디어를 정리하면 N을 1로 만들기 위해 필요한 연산 횟수는 

DP[N] = DP[N/3] + 1 혹은

DP[N] = DP[N/2] + 1 혹은

DP[N] = DP[N-1] + 1

세 가지 중 하나가 될 수 있다.

문제의 조건은 최소 연산 횟수를 구하라는 것이니까 저 셋 중 최소값을 구해야 한다. 

 

3. 상향식 접근방식인 타뷸레이션 방식으로 N의 최소값인 1부터 N까지 횟수 계산을 시작해서

다음 숫자는 몇 번의 연산이 필요한지 더해가는 방식으로 접근할 것이다. 

그런데 1은 1로 만드는 데 필요한 연산 횟수가 0이라는 것을 알고 있다. 

그렇다면 각 숫자의 연산 횟수를 저장할 DP 배열을 생성할 때 모든 원소를 0으로 초기화하면

N이 1일 때 필요한 연산 횟수를 알아내기 위해 연산할 필요가 없다. 

N이 2일 때부터 계산을 해 보면 된다.

반복문으로 DP 배열의 2번째 인덱스부터 계산하면서 연산 횟수의 최소값을 인덱스에 저장한다. 

 

---

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<int> counts(N + 1, 0);
    for (int i = 2; N >= i; i++)
    {
        //i = 2 일 때 counts[1] = 0 이다. 
        //2를 1로 만들기 위해서는 1을 빼면 된다. 즉 1번이 최소 연산 횟수 
        //counts[1]에는 0이 들어있으니까 counts[2]에는 1이 들어갈 것임 
        counts[i] = counts[i-1] + 1;
        if (0 == i % 3) //모든 조건을 적절히 사용했을 때의 최소값을 구해야 하기 때문에 나머지 케이스도 모두 확인
            counts[i] = min(counts[i], counts[i/3] + 1);
        if (0 == i % 2)
            counts[i] = min(counts[i], counts[i/2] + 1);
    }
    
    cout << counts[N];
    
    return 0;
}