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

문제

 

 

풀이과정

 

DP를 사용하여 강아지 마리수에 대한 최소 행동횟수를 구할 수 있다.

 

문제 이해

N = 7, M = 1, A = 2, B = 3 인 경우

총 7마리의 강아지를 구하고, 닫힌 구간은 3 ~ 4이며, 한 번의 행동으로 추가할 수 있는 강아지 수는 2 또는 3이다.

여기서 A또는 B 행동을 통해 닫힌 구간에 해당되면 강아지는 0마리가 된다. => 해당 구간의 마리수는 만들 수 없다.

 

문제 접근

• DP 배열 정의
  • dp[i] = i 마리를 만들기 위한 최소 행동 횟수 
  • 닫힌 구간은 -1로 설정
• 조건 단순화하기 위해 A, B 통일
  • A 는 작은 수, B는 큰 수로 통일
• 점화식
  • i - A 또는 i - B  에서 왔는지를 검사
    • 둘 다 불가능하면 -1,
    • 둘 중 하나라도 가능하면 그 중 최소값 + 1

 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        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());

        // A < B로 통일
        if (A > B) {
            int temp = A;
            A = B;
            B = temp;
        }

        int[] dp = new int[N + 1];

        // 닫힌 구간 -1 처리
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            for (int j = start; j <= end; 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) {
                dp[i] = (dp[i - A] == -1) ? -1 : 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;
                }
            }
        }

        bw.write(dp[N] + "");
        bw.flush();
        bw.close();
    }
}