공부 기록/알고리즘 풀이
[240715] BOJ 16432 떡장수와 호랑이
IsItGettingBetter?
2024. 7. 15. 21:54
문제
https://www.acmicpc.net/problem/16432
소스코드
(접은글을 열어주세요)
더보기
더보기
package Week_26.BOJ_16432;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class BOJ_16432 {
static int solve(int n, int[][] dp, boolean[][] arr) {
int idx1, idx2;
int check = -1;
for (int i = 1; i < n + 1; i++) {
// 이전 과정에서 가능했던 2가지 경우 확인
idx1 = 0;
idx2 = 0;
check = -1;
if(i > 1) {
for (int j = 1; j < 10; j++) {
if (dp[i - 1][j] > 0) {
idx2 = idx1;
idx1 = j;
}
}
} else idx1 = 10;
for (int j = 1; j < 10; j++) {
// 이번에 j를 선택할 수 있을 때
if (arr[i][j]) {
// 지난번에 가능했던 어떤 경우 idx1과 같은 종류의 떡이라면
if (j == idx1) {
// idx2의 떡이 존재하는지 확인하여 가능 여부 체크, 백트래킹을 위한 떡 체크
if (i == 1 || dp[i - 1][idx2] > 0) {
dp[i][j] = idx2;
check = j;
}
// 지난번에 가능했던 idx1과 다른 떡이 하나라도 있었다면 백트래킹을 위한 떡 체크
} else if (idx1 != 0) {
check = j;
dp[i][j] = idx1;
}
}
}
// i번째 날에서 떡을 주는게 불가능했다면 종료
if (check == -1) return -1;
}
return check;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
boolean[][] arr = new boolean[n + 1][10];
int m;
for (int i = 1; i < n + 1; i++) {
st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
for (int j = 0; j < m; j++) {
arr[i][Integer.parseInt(st.nextToken())] = true;
}
}
int[][] dp = new int[n + 1][10];
int tmp = solve(n, dp, arr);
if (tmp != -1) {
ArrayDeque<Integer> ans = new ArrayDeque<>();
for (int i = n; i > 0; i--) {
ans.offerLast(tmp);
tmp = dp[i][tmp];
}
StringBuilder sb = new StringBuilder();
while (!ans.isEmpty()) {
sb.append(ans.pollLast()).append("\n");
}
System.out.print(sb);
} else {
System.out.println(-1);
}
}
}
소요시간
90분
알고리즘
DP
풀이
- 문제 이해
- 1번부터 9번까지의 떡 중 날마다 만드는 떡의 종류가 주어진다.
- 어제 호랑이에게 준 떡은 다시 줄 수 없고, 줄 수 있는 떡이 없다면 잡아먹힌다.
- 바로 전날에 준 떡의 종류가 오늘 떡을 줄 수 있는지 여부에 영향을 미친다.
- DFS, 또는 DP로 풀이 가능하다.
- 풀이 과정
- DP로 풀고자 노력하였다.
- 전날 줄 수 있는 떡이 한종류라면, 오늘 줄 수 있는 떡에 제한이 있게 된다.
- 전날 줄 수 있는 떡이 두 종류 이상이라면, 오늘 줄 수 떡에 제한이 없어진다.
- 따라서 전 날 줄 수 있는 떡이 무엇이 있었는지 확인해보고, 오늘 생산한 떡을 줄 수 있는지를 판단하는 방법으로 문제를 풀이하였다.