[백준] 1463번: 1로 만들기 | C++ 풀이

# 문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

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

 

 

이미지를 클릭하면 백준 문제 페이지로 이동합니다.

 

 

---

 

# 풀이

오늘도 DP 풀이!

바로 정답 소스 코드를 확인해보자.

 

#include <iostream>
#include <algorithm>
using namespace std;

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

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

    cout << D[n];
    return 0;
}

 

지난 번 돌 게임을 풀고 와서 그런지 방법을 떠올리는 게 어렵진 않았다.

돌 게임과 유사하게 접근하되 이번에는 방법이 세 개니 min값만 잘 따져주면 된다.

 

 

int n;
cin >> n;

int D[n+1] = {};
D[1] = 0;

 

입력 n을 받고, 1부터 n까지 따져보기 위해 DP 테이블의 크기는 n+1로 설정해주었다.

혹시 모를 쓰레기 값을 초기화하기 위해 0으로 초기화 해주었지만, D[1]은 명시적으로 0을 넣어주었다.

이번 문제는 D[2], D[3]도 1이라는 것을 아주 쉽게 알 수 있지만 for문을 통해 채우는 것도 쉽게 가능하여 값을 명시적으로 넣어주진 않았다. 이 부분은 본인 취향에 맞게 진행하면 될 것 같다. 대신 이때는 뒤에 나올 for문의 조건식들을 조금 조정해주어야 한다.

 

 

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

 

바로 Bottom-up DP 테이블 구성으로 진입! 인덱스는 1부터 n까지 돌리면 된다.

 

해당 문제에서는 어떠한 수에 대해 선택할 수 있는 방법이 세 가지 있다. 

1. 1을 빼주기
2. 2로 나누어 떨어질 경우 2로 나눠주기
3. 3으로 나누어 떨어질 경우 3으로 나눠주기

따라서 각각의 경우를 모두 계산해보고, 가장 작은 값을 선택해 출력해주면 된다.

 

1을 빼는 경우는 따로 걸려있는 조건이 없으므로, 1을 빼는 경우를 먼저 D[i]로 설정해주었다.

예: D[2] = D[1] + (1을 빼는 횟수 카운트) = D[1] + 1 = 1

 

그 다음 2로 나누어지는 경우, 1을 빼는 경우의 횟수와 비교해 더 작은 횟수를 가진 걸 D[i]로 설정

예: D[2] = min((앞서 계산한 값) 1, D[2/2] + 1) = 1

 

똑같이 3으로 나누어지는 경우에도, 위에서 결정된 D[i]값과 비교해 더 작은 횟수를 가진 걸 D[i]로 업데이트 해주면 된다.

예: D[3] = min(D[2], D[3/3] + 1) = 1

 

 

 

 

 

 

---

 

 

 

 

1463번: 1로 만들기