[BaekJoon/백준] 1463번 | 복습 1회 완료

 

이전 문제들과 비슷하게, '해당 인덱스까지의 최솟값 / 최댓값' 이런 형태로 문제를 푸는 Bottom - up 방식이였다.

 

 

사실 문제를 처음 읽을 땐, 건방지게도 문제가 쉬워 보였다.

 

그냥 규칙만 잘 찾으면 문제가 풀리겠구나 라는 생각이였고, 실제로 1부터 25까지 숫자들 경우를 구해보면서 규칙을 찾은 것만 같았다.

이를 토대로 식을 구성하여 코드를 짰고, 넣자마자 1퍼도 안가서 탈락.

 

내 표본들에 의해서는 매우 정확하다고 생각했기에, 당연히 맞을거라고 생각했다.

 

하지만 그런 나에게 뒤통수를 세게 후려주듯이, 식을 세우는 데에 있어 엄청난 반례들이 존재했다.

 

이 문제의 핵심은, '나누어 떨어진다고 해서, -1 한 것보다 항상 작진 않다는 것' 이라는 반례가 있었다.

 

나열되는 최솟값의 규칙은 이러하다.

순서대로 나열되는 a b가 있을 때, b는 a + 1회의 값보다 클 수 없다.

(b의 값은 나누어 떨어져서 얻는 값이거나, 그렇지 않은 경우 -1을 빼서 얻는 값 + 1회이므로)

 

나 같은 경우엔, 6으로 나누어 떨어질 때에도 (2와 3의 최소공배수),

3으로 나누어 떨어지더라도 2의 경우가 더 빠를 수도 있을 것 같아서(항상 a < b는 아니므로) 2와 3의 경우를 비교하는 코드를 실행해봤고, 3으로 나눈 경우가 무조건 더 작을 것이라는 전제 하에 3 -> 2 우선순으로 한 번만 실행하는 코드도 실행해봤다. 근데 후자일 경우에도 정답처리가 되었다.

 

경우 1 -> 2와 3으로 동시에 나누어 떨어지더라도, 두 경우를 비교

// 문제 자체는 쉬워보이는데 반례가 너무 많다.


#include <iostream>
#define MIN(a, b) ((a<=b)?a:b)
using namespace std;

int x[1000001] = {0, 0, 1, 1, }; // 1 ~ 100000 까지, 각 인덱스의 값은 각 값을 1을 만드는 데의 최소연산횟수를 가짐.
int N;

int main() {
    cin >> N;
    
    for(int i = 4; i <= N; i++) {
        x[i] = x[i - 1] + 1;
        
        if(i % 3 == 0) {
            x[i] = MIN(x[i], (x[i/3] + 1));
        }
        if(i % 2 == 0) {
            x[i] = MIN(x[i], (x[i/2] + 1));
        }
    }
    cout << x[N];

    
}

정답처리.

 

경우 2 -> 3으로 나누어떨어지면 2 경우보다 무조건 작다는 전제

// 문제 자체는 쉬워보이는데 반례가 너무 많다.


#include <iostream>
#define MIN(a, b) ((a<=b)?a:b)
using namespace std;

int x[1000001] = {0, 0, 1, 1, }; // 1 ~ 100000 까지, 각 인덱스의 값은 각 값을 1을 만드는 데의 최소연산횟수를 가짐.
int N;

int main() {
    cin >> N;
    
    for(int i = 4; i <= N; i++) {
        x[i] = x[i - 1] + 1;
        
        if(i % 3 == 0) {
            x[i] = MIN(x[i], (x[i/3] + 1));
        }
        else if(i % 2 == 0) {
            x[i] = MIN(x[i], (x[i/2] + 1));
        }
    }
    cout << x[N];

    
}

정답처리. 속도는 경우 1보다 당연히 조금 더 빠르다.

 

다른 분들의 코드를 많이 참고해보니, 1의 경우가 안전한 방법인 것 같다.

 

 

참고

www.acmicpc.net/board/view/19169#comment-103748

글 읽기 - 1로 만들기 FAQ

 

---

2021.02.24 복습

다시풀어보았다. 다시 푸는데 살짝 애먹었다. 이전에도 내가 이 문제를 직접 풀지 못했던 만큼, 어려웠던 것 같다.

역시나 위에 정리해놨던 코드보다는 다소 복잡하게 풀어버렸다.

#include <stdio.h>
#define MIN(a,b) ((a<=b)?a:b)

int N;
int dp[1000001] = {1, };

int main() {
    
    scanf("%d", &N);
    
    
    for(int i = 2; i <= N; i++) {
        dp[i] = 1000001;
        
        if(i % 3 == 0)
            dp[i] = MIN(dp[i / 3], dp[i - 1]) + 1;
        if(i % 2 == 0)
            dp[i] = MIN(dp[i], MIN(dp[i / 2], dp[i - 1]) + 1);
        if(dp[i] == 1000001)
            dp[i] = dp[i - 1] + 1;
    }
    
    printf("%d", dp[N]);
}


/*
 
 A. 3으로 나누어 떨어지면 나눈다.
 B. 2로 나누어 떨어지면 나눈다.
 C. 1을 뺀다.
  
 A & B & C 를 조합해서, 모든 경우를 만들었다.
 
 */