[백준]1563번 개근상

• 문제에서 주어지는 것은 N 밖에 없다.

• 출석, 지각, 결석

  • 출석 : O
  • 결석 : A
  • 지각 : L

• 문제 조건

  • 개근상에서 제외되는 경우
    1. 지각을 2번 {이상}
    2. 결석을 세번 {연속}
  • 💥💥💥정답을 1000,000으로 나눈 나머지를 출력한다 💥💥💥

• 구해야 하는 것

  • N이 주어질 때, { 개근상을 받을 수 있는 출결정보의 개수 }

• 문제 해결

  • 일단 그냥, 개근상을 받는 경우에 집중 해 본다면 , N과 상관없이
    1. 지각을 총, 1번 이하 💥💥 AND💥💥
       • 지각 0번
       • 지각 1번
    2. 결석을 연속으로는 세 번 "이상"해선 안된다.
  • 그냥 경우의 수라고 생각하면, 3^N가지의 경우의 수가 생기는 것이다. 그런데 N은 최대 1000이기 때문에 절대 불가능하다.
    • 모든 경우를 "직접 다 생성" 하는 문제는 절대 아니다.
    • 즉, 단순한 백트랙킹으로는 풀 수 없다.
  • 문제에서 1000,000으로 나눈 나머지를 출력하라는 것은, 단계별로 구해가면서 1000,000으로 나누는 일이 생길 수 있다는 것이다 .
  • 다이나믹 프로그래밍 문제 같다. 약간 비즈공예 때의 냄새가 난다.
    • {cache[i] 에는 i일까지 만드는 최대 경우의 수 를 구한다.} 로 하면 해결은 안 될 것 같다.
    • 다차원의 캐시를 생성해야 할 것 같다.
    • i일의 것을 선택 시, { 이제까지 총 지각한 횟수A(최대 1번) } , { 이제까지 i-1까지 결석한 횟수 B(연속 최대 2번)(즉, i-2에서 A, i-1에서 A를 선택했다면 i로 올 때면 2가 넘어와야하고, i-2는 A, i-1은 L을 했다면, i로 넘어올 때 0이 넘어와야 한다. ) } ,{ 현재까지의 총 날짜} 정보를 전달 받아야 한다..

❌나오는 경우들을 이해해보자

• late는 0 또는 1만 가능
  abs는 0,1,2만 가능
• abs가 0이거나 1일 경우 --> 현재도 abs 가능하며, abs ++ 를 넘김
  abs가 2일 경우 --> 현재 abs 불가능하며, abs는 0을 넘김
  late가 0인 경우 --> 현재도 late가능하며, late++를 넘김, abs는 0을 넘긴다. (연속이 깨졌기 때문)
  late가 1인 경우 --> 현재 late 절대 불가능하며, 원래의 late(1)을 넘김.
• 즉 종합하면! 현재에서 ,
  late 선택 가능한 경우들 : late가 0인 경우만 가능
  abs 선택 가능한 경우들 : abs가 0,1인 경우 가능.
  O 선택이 가능한 경우들 : 위의 경우들에도 충분히 선택 가능하다.
  late나 O를 선택 하는 경우 --> abs는 0을 넘겨야 한다.

• 나는 이런 문제는 "비즈공예"가 떠오른다. 그 문제를 풀고도 그 문제처럼 풀려고 머리를 굴려도 잘 생각이 나지 않긴 했다. DP문제에 매우 취약해서 이 문제 또한 매우 오래 걸렸다.

또한 이 문제는 자료형도 고려해줘야한다. 💥💥 Long으로 해주더라도 값이 초과되 기 때문에 연산 과정 중간에서도 100만으로 나누는 것이 필요하다. 따라서 이러한 과정을 해 주어야 한다.

• (a+b)%m = (a%m + b%m)%m 이다.

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

    public class Main{

        public static int n;
        public static long [][][] cache = new long[1001][2][3]; //  total, late, abs 이다. late는 0,1 가능 abs는 0,1,2 가능
        public static void Setting() throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(br.readLine());
            // Setting cache (value : -1)
            for(int i=0;i<cache.length;i++){
                for(int j=0;j<cache[0].length;j++){
                    Arrays.fill(cache[i][j],-1);
                }
            }

        }
        public static long dp(int total, int late, int abs){
            if(total == n) return 1;
            if(cache[total][late][abs]!=-1)return cache[total][late][abs];
            long sum = 0 ;
            long temp = 0;

            // late나 O 선택시, 지각 연속이 깨지는 것이기 때문에 abs에는 0이 오게 된다.
            // late는 전체에서 지각이 두 번 이상 있으면 안 되는 것 이기 때문에 , abs나 O를 선택한다고 late를 초기화시키진 않는다.
            // late 선택도 가능한 경우
            if(late == 0) {

                temp = dp(total+1,late+1,0);
                sum = proc(temp,sum);
            }
            // abs 선택도 가능한 경우 
            if(abs<2) {
                temp=dp(total+1,late,abs+1);
                sum = proc(temp,sum);
            }
            // O를 선택하는 경우
            temp = dp(total+1,late,0);
            sum = proc(temp,sum);
            cache[total][late][abs]=sum;
            //System.out.println("TOTAL "+total +", late: "+late+", abs: "+abs);
            System.out.println("cache[total][late][abs] = " + cache[total][late][abs]);
            return sum;

        }
        public static long proc(long temp, long sum){
            temp %=1000000;
            sum%=1000000;
            return (temp+sum)%1000000;
        }

        public static void main(String[] args) throws IOException{
            Setting();
            dp(0,0,0);
            System.out.println(cache[0][0][0]);
        }

    }

• 여전히 동적 프로그래밍 문제를 정말 못 푼다. 이제는 DP로 풀어야 하는 구나 감이 먼저오는 편이지만, 비즈공예 문제를 푼 후에도 ,이 문제도 풀이법이 바로 떠오르지가 않는다.아 슬프다 ㅎㅎ 괜찮다 내가 DP를 진짜 못하고 있기 때문인데, 마침 그냥 고른 문제가 DP라니!!마침 나한테 필요한 문제가 이렇게 뜨다니!! 행복하다!! 적어도 아 DP로 풀어야겠구나가 바로 떠올랐고, 이번만은 혼자서 다 풀어보자 생각하고, 필요한 정보는 무엇일까 고민하고, 경우를 나눠보았다. 재귀의 흐름이 머리속에서 잘 떠오르지 않는 편이라 이렇게 해서 답이 나오긴 하는걸까?? 생각하는데 많이 고민한다. 결국 return 1을 통해서 경우의 수가 쌓인다는게 아직 익숙하지 않다.
• 나한테 어려운 문제라면 나에겐 어려운 문제다. 그런 문제는 열받아서 때려치고 일주일 정도 후에서나 겨우 마무리 지으러 오는 경우도 많은데 오늘은 3시간..만에라도 풀었다는것에 의의를 둬야겠다 ㅎ..
• 나는 DP를 정말 못한다 그러니까 많이 풀어봐야 한다.