백준 1563번 - 개근상(★★★ / XO / 2) : Python / JavaScript

기운찬곰·2021년 3월 30일

DFS/BFS 다이나믹프로그래밍 백준 재귀함수

백준2

목록 보기

13/17

개요

풀이 시간 : 30분
시간 제한 : 2초
메모리 제한 : 128 MB
기출 : backjoon
링크 : https://www.acmicpc.net/problem/1563

문제

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다.

출결사항이 기록되는 출결은 출석, 지각, 결석이다.

개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다.

한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결정보는 총 43가지이다.

한 학기는 N일이다. N이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000보다 작거나 같다.

출력

첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다.

해결방법

문제 이해하기

와... 생각보다 어렵다. 30분 동안 고민했는데 실패... 다이나믹 프로그래밍인거는 얼핏 생각은 했지만 어떻게 메모리제이션해서 풀어야 할지 감이 좀처럼 잡히지 않았다.

알고리즘

이 문제는 DFS + 재귀 + 다이나믹이다. 사실 이런 형식의 문제풀이를 몇번 마주치긴 했었다. 그때마다 번번히 실패하고 있지만 말이다. 아무래도 내가 재귀가 약하다 보니까...ㅠㅠ

일단 메모리제이션 설계부터 하는게 중요하다.

dp = [[[-1 for absent in range(3)] for late in range(2)] for day in range(n)]

보는것처럼 (N - 1) * 2 * 3 형식의 3차원 배열이다. 이런식으로 설계한 이유는 연속해서 결석을 했는지 저장하고, 또한 지각을 두번이상 했는지 여부를 조사하기 위함이다.

그리고 나서 DFS 재귀 탐색을 시작하면 된다. 하나씩 깊이 들어가서 dp를 업데이트하면서 차근차근 올라가면 된다. (코드를 보면 쉽게 이해가 갈 것이다)

💻 참고 : https://sosoeasy.tistory.com/95

Python

정답 코드

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(day, late, absent):
    # 지각을 2번 or 결석 연속 3번한 경우
    if late == 2 or absent == 3:
        return 0

    # 개근을 한 경우
    if day == n:
        return 1

    if dp[day][late][absent] == -1:
        # 참석 or 지각 or 결석
        attend = (
            dfs(day + 1, late, 0)
            + dfs(day + 1, late + 1, 0)
            + dfs(day + 1, late, absent + 1)
        )
        dp[day][late][absent] = attend
        # print(day, late, absent, attend)
        return attend
    else:
        return dp[day][late][absent]


if __name__ == "__main__":
    n = int(input())
    dp = [[[-1 for absent in range(3)] for late in range(2)] for day in range(n)]

    print(dfs(0, 0, 0) % 1000000)
    # print(dp)

✍️ 에휴... 이런 문제는 이제 풀 수 있어야 하는 단계여야 하는데... 좀처럼 늘지 않는구나ㅠㅠ

JavaScript

내 코드

// 출석-지각-결석
function countAttend(o, l, a) {
  // 지각을 두번 이상 한 경우 or 결석을 연속 세번 한 경우
  if (l === 2 || a === 3) {
    return 0;
  }
  // 개근한 경우
  if (o === n) {
    return 1;
  }

  if (dp[o][l][a] !== 0) {
    return dp[o][l][a];
  }

  // 다음이 그냥 출석인 경우
  dp[o][l][a] += countAttend(o + 1, l, 0);
  // 다음이 지각인 경우
  dp[o][l][a] += countAttend(o + 1, l + 1, 0);
  // 다음이 결석인 경우
  dp[o][l][a] += countAttend(o + 1, l, a + 1);

  return dp[o][l][a] % 1000000;
}

const n = Number(input());
const dp = Array.from(Array(n), () =>
  Array.from(Array(2), () => Array(3).fill(0))
); // 1000(출석) * 2(지각) * 3(결석연속)

console.log(countAttend(0, 0, 0)); // 출석-지각-결석