[240715] BOJ 16432 떡장수와 호랑이

문제

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로 풀고자 노력하였다.
  • 전날 줄 수 있는 떡이 한종류라면, 오늘 줄 수 있는 떡에 제한이 있게 된다.
  • 전날 줄 수 있는 떡이 두 종류 이상이라면, 오늘 줄 수 떡에 제한이 없어진다.
  • 따라서 전 날 줄 수 있는 떡이 무엇이 있었는지 확인해보고, 오늘 생산한 떡을 줄 수 있는지를 판단하는 방법으로 문제를 풀이하였다.