문제


풀이과정
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
- i - A 또는 i - B 에서 왔는지를 검사
코드
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();
}
}
'Algorithm' 카테고리의 다른 글
| [Programmers] 2019 KAKAO BLIND RECRUITMENT 후보키 - JAVA (1) | 2025.08.28 |
|---|---|
| [Programmers] 2021 카카오 채용연계형 인턴십 표 편집 - JAVA (2) | 2025.08.27 |
| [Programmers] 2021 KAKAO BLIND RECRUITMENT 순위 검색 - JAVA (0) | 2025.08.21 |
| [백준] 6497. 전력난 - JAVA (2) | 2025.08.20 |
| [백준] 1783. 병든 나이트 - JAVA (3) | 2025.08.13 |