[백준/27971] 강아지는 많을수록 좋다- JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버1
출처 : 백준 - 강아지는 많을수록 좋다

🦧 문제 풀이 접근

DP를 이용해 강아지에 마리수에 따라 최소한의 행동 횟수를 구한다.
이때 행동 횟수를 구할 수 없는 경우 (닫힌 구간에 포함되어 있거나 A, B 마법보다 작을 경우) -1 값을 넣는다.

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        if(A>B) {
            int swap = A;
            A=B;
            B=swap;
        }
        int[] dp = new int[N+1];
        dp[0]=0;
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            for(int j=s;j<=e;j++) {
                dp[j] = -1;
            }
        }
        for(int i=1;i<=N;i++) {
            if(dp[i]==-1)
                continue;
            if(i<A) {
                dp[i] = -1;
            }
            else if(i<B) {
                if(dp[i-A]==-1)
                    dp[i] = -1;
                else
                    dp[i] = dp[i-A]+1;
            }
            else if(dp[i-A]==-1 && dp[i-B]==-1)
                dp[i] = -1;
            else if(dp[i-A]==-1)
                dp[i] = dp[i-B]+1;
            else if(dp[i-B]==-1)
                dp[i] = dp[i-A]+1;
            else
                dp[i] = Math.min(dp[i-A],dp[i-B])+1;
        }
        System.out.println(dp[N]);
    }
}

🥇 결과

🎓 느낀점

그래프 문제지만 DP를 이용해 풀었다. 그래프보다 DP로 했을때 효율적이라고 판단이 되었다.