백준 1463번 C/C++

1463번 백준 공부

첫번째 오답은 이러한 형태였다.

#include <stdio.h>

int main() {

int a;
int min;
int count;

scanf_s("%d", &a);

if (a == 1) {
    return 0;
}

while (a != 1) {
    if ((a - 1) % 3 == 0) {
        a = a - 1;
        a = a / 3;
        count++;
    }
    else if (a % 3 == 0) {
        a = a / 3;
        count++;
    }
    else if (a % 2 == 0) {
        a = a / 2;
        count++;
    }
    else {
        a = a - 1;
    }
}
printf("%d", count);

system("pause");

}

이러한 형태가 되면 실패하는 예시로는 32가 있었다.
32->16->15->5->4->2->1
하지만
32->16->8->4->2->1 의 값이 더 최솟값이었다.

다른 방식으로 while을 변경을 하거나 if 문을 변경을 해보려 했지만 count의 최솟값을 구해야했기에

while 반복문의 순서를 바꿀 필요성이 있었고
어느 부분에서 고쳐야할지 생각이 나지 않았다.
그래서 아예 새로운 방식으로 생각을 했다

각 count는 더하면서 count를 비교해서 count가 작은 수만 마지막에 살리는 방식을 택했다.
그 방식의 코드는 이와 같다.

#include <stdio.h>

int main() {

int a;
int count;


scanf("%d", &a);

count = algori(a);

printf("%d", count);

}

int min(int i, int j)
{
if (i > j) {
return j;
}
else return i;
}

int algori(int a) {
if (a == 1) return 0;
if (a % 3 == 0) { //3으로 나눠지는 경우
return min(1 + algori(a / 3), 2 + algori((a - 1) / 2)); //첫 숫자는 count용, 1번 파라미터 - 3나누기 / 2번 파라미터 - 1뺴고 2나누기
}
if (a % 2 == 0) { //2로 나눠지는 경우
return min(1 + algori(a / 2), 1 + algori(a-1)); //첫 숫자는 count용, 1번 파라미터 - 2나누기 / 2번 파라미터 - 1빼기
}
return 1 + algori(a - 1); //1 빼기
}

이렇게 되면 첫 코드와는 다른 점이 첫 코드는 하나의 경우만 발견을 할 수 있었지만
이 코드의 경우에는 나누어 떨어지는 가정에서 최솟값을 구하기 때문에 2가지씩 나올 수 있는 가정을 생각해서
min이라는 함수를 활용하여 count를 각각 비교를 하며
마지막엔 모두 1이 나오기 때문에 1에서부터 거슬러 올라오면서 count를 늘려갈 것이고 동일한 숫자가 되었을 때
count가 더 크다면 최솟값이 아니기 때문에 탈락이 되며 마지막 return이 된다.
그로 인해 main의 count에 최솟값이 들어가게 되며
제출을 하였을 때 정답이 되었다.