글 읽기 - 1463번 제 코드좀 봐주시기 바랍니다 ㅜ

sesdesa 6년 전 0

이제 막 알고리즘을 공부하기 시작해서 다이나믹 프로그래밍을 열심히 공부해보려 하고 있습니다

일단 dp로 풀어야 한다는 것 (이 전의 값들을 토대로)을 깨달은 것만으로도 희열을 느꼈습니다...(초보라서...)

근데 최소 값을 찾는 것에서 예외 상황이 여러개 생겨서 하나하나 찾아가면서 코드를 고쳐줘도 검사 중간에 틀렸습니다가 뜨더라구요..!!

혹시 제가 놓치고 생각한 부분이 있을까요?! ㅜㅜ 친절한 답변 부탁드리겠습니다! 감사합니다!

import java.util.Scanner;

public class Main {

    static int[] dp = new int[1000001];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;

        int n = scan.nextInt();
        for(int i = 4; i <= n; i ++){
            if(i%3 == 0){
                dp[i] = min(dp[i/3] + 1, dp[i-1]+1);
            }else if((i-1) %3 == 0){
                if(i%2 == 0){
                    dp[i] = min(dp[(i-1)] + 1, dp[i/2] + 1);
                }else{
                    dp[i] = dp[i-1] + 1;
                }
            }else if(i%2 == 0){
                dp[i] = dp[i/2] + 1;
            }else{
                if((i-2)%3 == 0){
                    if((i-1)%2 == 0){
                        dp[i] = min(dp[(i-2)] + 2, dp[(i-1)] + 1);
                    }else{
                        dp[i] = dp[(i-2)] + 2;
                    }
                }
            }
        }
        System.out.println(dp[n]);
    }

    static int min(int x, int y){
        if(x <= y){
            return x;
        }
        return y;
    }
}

djm03178 6년 전 1

조언을 좀 드리자면 14~34번째 줄의 조건들이 너무 복잡합니다. 이렇게 많은 조건을 쓸 필요가 없습니다. i번째 루프에서는 오로지 dp[i]에만 신경쓰면 됩니다.

그리고, i가 3의 배수더라도 2로 나누어떨어질 때 2로 나누는 것이 더 빠른 경우가 있을 수 있습니다.

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

문제

문제

출처

ICPC

1463번 제 코드좀 봐주시기 바랍니다 ㅜ

sesdesa 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말