M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 1463 - 1로 만들기

최대 1 분 소요

문제

백준 1463 - 1로 만들기 풀러가기

문제 분석

이 문제는 큰 문제를 작은 문제로 쪼갤 수 있다.

그리고 이 작은 문제들은 서로 겹치고, 작은 문제의 정답은 항상 같다.

  • 10을 1로 만드는 연산의 최솟값은 항상 같다.
    • 11을 1로 만든다면 10을 최솟값으로 만드는 과정을 포함하고 있다.

문제 풀이(c++)

  1. 전체 코드(TOP-DOWN 방식)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    #include <cstdio>
     
    using namespace std;
     
    int d[1000001];
     
    int go(int n) {
        if (n == 1) {
            return 0;
        }
        if (d[n] > 0) {
            return d[n];
        }
     
        d[n] = go(n - 1) + 1;
     
        if (n % 2 == 0) {
            int temp = go(n / 2) + 1;
            if (d[n] > temp) {
                d[n] = temp;
            }
        }
     
        if (n % 3 == 0) {
            int temp = go(n / 3) + 1;
            if (d[n] > temp) {
                d[n] = temp;
            }
        }
     
        return d[n];
    }
     
    int main() {
     
        int n;
     
        scanf("%d", &n);
     
        go(n);
     
        printf("%d", d[n]);
     
        return 0;
    }
    		cs





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고