54. C++ 백준 1463번 자세한 설명

 

안녕하세요. 코딩하는 덕구입니다. C++백준 1463 번 1로 만들기 입니다.

다이나믹 프로그래밍 문제입니다.

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

1463번: 1로 만들기

 

 

예를들어 숫자 10을 연산 1, 2, 3 번을 이용해 1을 만든다고 하면

10 -1, = 9

9/3 = 3

3/3 = 1 

3단계로 연산할 수 있습니다.

이때 9에서 연산들을 이용하여 1로 가는 횟수

3에서 연산들을 이용하여 1로 가는 최소 횟수 등이 필요하게 되죠

결국 입력값보다 작은수부터 연산 최소 횟수를 구해서 저장하면

큰 수에서 최소값을 찾기 위해 모든 경우의 수를 구해서 비교 하는게 아닌

반복되고 불필요한 연산횟수를 줄일 수 있습니다. 

 

어떤 숫자의 최소 연산을 계산할 때 3가지의 경우가 있습니다.

1. 1을 빼주면 미리 계산했던 값이 나오는 경우

2. 2로 나눠지는 경우

3. 3으로 나눠지는 경우

이 3가지의 경우 중 어떤 값이 최솟값인지 모르기 때문에 직접 계산을 해서 가장 작은 값을 해당 cnt 의 index에

넣어주면 됩니다. 

 

int cnt[1000001] = {0,};
cnt[1] = 0;
cnt[2] = 1;
cnt[3] = 1;

배열의 index를 각 숫자로, 내용을 최소 연산 횟수로 저장할 배열 cnt를 선언하고,

1, 2, 3 의 경우에 필요한 연산 횟수를 기본값으로 넣어놓습니다.

1 은 연산하지 않아도 1이므로 0,

2는 2-1=1 혹은 2/2=1, 1회가 필요하므로 1

3은 3/3 = 1, 1 회가 필요하므로 1입니다.

 

for (int i = 4; i<=N; i++){
    cnt[i] = cnt[i-1] + 1; 

1, 2, 3 의 경우에 미리 값을 구해서 저장했기 때문에

for문을 4부터 시작하여 숫자 4의 경우를 계산해서 저장해봅시다.

먼저 1번째 경우인 -1의 경우를 계산해서 넣습니다.

바로 전 수의 최소 연산 횟수에 -1을 했으므로 바로 전 수에 +1 을 하면 최소 연산이겠죠.

이 값을 일단 저장합니다.

 

 

if (i % 3 == 0) cnt[i] = min(cnt[i/3] + 1, cnt[i]);
if (i % 2 == 0) cnt[i] = min(cnt[i/2] + 1, cnt[i]);

2, 3번의 경우입니다. 2나 3으로 나눠지면 나누고, 연산횟수를 1 카운트 합니다.

이 경우 처음 연산과 3으로 나눈 연산 중 더 작은 값이 최소값으로 업데이트 됩니다.

두번째 if 문에서도 첫번째 if문을 통해 나온 최소값과, 2 로 나눠진 수의 최솟값을 비교해서 업데이트 합니다.

 

최종적으로 cnt[i]는 숫자 i를 1로 만들기 위한 최소값이 들어있게 됩니다.

cout << cnt[N];

이것을 출력하면 정답이 되겠죠.

 

 

백준 1463번 C++ 최종 코드입니다.

#include<iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    int cnt[1000001] = {0,};
    cnt[1] = 0;
    cnt[2] = 1;
    cnt[3] = 1;

    for (int i = 4; i<=N; i++){
        cnt[i] = cnt[i-1] + 1;

        if (i % 3 == 0) cnt[i] = min(cnt[i/3] + 1, cnt[i]);
        if (i % 2 == 0) cnt[i] = min(cnt[i/2] + 1, cnt[i]);
    }
    cout << cnt[N];

    return 0;
}

 

백준 1463 번 C++ 이였습니다. 감사합니다.