글 읽기 - 1463번 탑 다운 방식에 대해 질문 있습니다.

specimen 5년 전 0

1463번을 탑 다운 방식으로 푼 예제 입니다.

소스에 대한 이해는 되는데 8번과 같은 생각을 어떻게 할까요...

수많은 연습 밖에 없겠죠..?

#include <iostream>
using namespace std;
int dp[1000000];
int fi(int n){
    if(n <= 1) return 0;
    if(dp[n] != -1) return dp[n];

    int times = fi(n-1) + 1;
    if(n%3 == 0) times = min(times, fi(n/3) + 1);
    if(n%2 == 0) times = min(times, fi(n/2) + 1);
    dp[n] = times;

    return times;
}
int main(void){
    int n;
    cin >> n;
    fill(dp, dp+1000000, -1);
    cout << fi(n) << endl;
    
}

djm03178 5년 전 0

dp[n]을 결정하는 식은 세 가지 중 하나이므로 그 중 하나로 먼저 설정해둔 것 뿐, 특별한 건 아닌 것 같습니다.

그리고 이 코드는 매우 위험한 코드입니다. 입력으로 100만이 들어왔을 때 배열의 범위를 초과한 주소에 접근하지만 운 좋게 에러가 나지 않았을 뿐입니다.

specimen 5년 전 0

답변 감사드립니다.!!

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

문제

문제

출처

ICPC

1463번 탑 다운 방식에 대해 질문 있습니다.

specimen 5년 전 0

djm03178 5년 전 0

specimen 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말