글 읽기 - c++ 1463 dp 이해가잘ㄹ안됩니다.

justking 6년 전 0

이 소스에서 12,13번줄 의 존재이유를 잘 몰르겟습니다. 저게 왜필요할까요

덧붙여서9~11번줄도 설명좀 해주세요 ㅠㅠ

#include <iostream>
#include <cstdio>

using namespace std;

long d[10000001];

long dp(long n){
    if( n == 1){
        return 0;
    }
    if(d[n] > 0){
        return d[n];
    }
    d[n] = dp(n-1) + 1;
    if(n%2 == 0){
        long temp = dp(n/2) + 1;
        if(d[n] > temp){
            d[n] = temp;
        }
    }
    if(n%3 == 0){
        long temp = dp(n/3) + 1;
        if(d[n] > temp){
            d[n] = temp;
        }
    }
    return d[n];
}

int main(){
    long n;
    scanf("%ld",&n);
    printf("%ld",dp(n));
    return 0;
}

djm03178 6년 전 1

9~11번째 줄: 수가 1에 도달했으면 더이상 연산을 수행할 필요가 없으니, 여기서 1로 만드는 데에 필요한 연산의 횟수는 0이라는 것을 나타냅니다.

12~14번째 줄: dp[n]이 0이 아니라는 것은, 이미 이전에 n에 도달하여 n을 1로 만드는 데에 필요한 최소 연산의 수를 구했다는 의미입니다. 따라서 추가적인 재귀호출 없이 바로 dp[n]을 리턴할 수 있습니다. 동적 프로그래밍의 핵심입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 1463 dp 이해가잘ㄹ안됩니다.

justking 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말