[백준] 1563번: 개근상(Java)

 

Notion에 정리한 글을 옮긴 것입니다.

1563번: 개근상

 

문제

---

 

 

풀이

---

완전탐색을 이용해야하지만, 완전탐색만 사용한다면 경우의 수가 O(3^1000)의 시간복잡도가 발생한다.

그래서 재귀적 접근(DFS) + dp ⇒ dp의 bottom-up방식을 사용하여 풀었다.

 

이 문제의 핵심은 점화식을 찾는 것인데, 간단한 예를 통해 알아보자.

한 학기를 3일이라고 하자.

지각(late)는 2일 이상이면 안되고, 결석(absent)은 연속 3일 이상이면 안된다.

dp[idx][late][absent] 3차원 배열을 생성하고,

idx는 현재 일 수, late는 지각 일 수, absent는 맨 마지막 인덱스부터 체크한 연속된 결석 일 수를 뜻한다.

그럼 OA는 dp배열로 나타내면 dp[2][0][1]이 된다.

그럼 생각해보자. OA_에 _는 뭐가 들어갈 수 있을까? 현재는 O, A, L 세가지 종류가 다 가능하다.

OAL, OAA, OAO 세가지 케이스를 dp배열로 나타내보면, dp[3][1][0], dp[3][0][2], dp[3][0][0]이고, OA의 경우는 이 세가지 케이스를 합친 값이 된다.

dp[2][0][1] = dp[3][1][0] + dp[3][0][2] + dp[3][0][0]

 

여기서 보면, 

 dp[idx][late][absent] = dp[idx+1][late+1][0] + dp[idx+1][late][absent+1] + dp[idx+1][late][0]

이라는 점화식을 얻어낼 수 있다.

 

하지만 문제에선, n이 변수이고, 재귀를 통해서 마지막까지 깊이 탐색을 한 후 그 값들을 모두 더해주고 계산해야 하기에, 점화식은 아래와 같이 변형된다.

dp[idx][late][absent] += dfs(idx+1, late+1, 0) + dfs(idx+1, late, absent+1) + dfs(idx+1, late, 0)

 

💡여기서 dfs의 return 값은 dp[idx][late][absent] % 1000000임(문제에서 1,000,000으로 나눈 나머지를 출력하라 했기 때문)

 

최후로 dfs(0,0,0)을 실행하면, dp[0][0][0]에 결과 값이 반환 됨.

 

 

코드

---

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

public class Main {
    static int n;
    static int dp[][][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        dp = new int[n+1][2][3];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 2; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        dfs(0,0,0);
        System.out.println(dp[0][0][0]);
    }

    public static int dfs(int idx, int late, int absent) {
        if(late == 2 || absent == 3) {
            return 0;
        }
        if(idx == n) {
            return 1;
        }
        if(dp[idx][late][absent] != -1) {
            return dp[idx][late][absent];
        }
        
        dp[idx][late][absent] = 0; // 방문기록 저장
        dp[idx][late][absent] += (dfs(idx+1, late+1, 0) + dfs(idx+1, late, absent+1)
                + dfs(idx+1, late, 0)) % 1000000;

        return dp[idx][late][absent] % 1000000;
    }
}