1주차_백준(1) - 신나는 함수 실행

▶문제

 

 

 

▶풀이

그대로 구현하면 값을 구하는데 오래 걸린다고 하였다..그 이유는 동일한 값을 계속 연산하기 때문이다.

따라서 dp 알고리즘을 통해 구현해서

 if dp[a][b][c] : return dp[a][b][c]

즉 dp[a][b][c]의 값이 존재한다면, 해당 값을 리턴하라는 기능만 추가해주면 시간 내로 풀 수 있다. 

 

※동적 계획(Dynamic Programming)

• 주어진 문제를 이보다 더 작은 크기의 문제들로 나눈 후, 이를 해결해 최종해에 다가가서 해를 찾는 알고리즘
• 주어진 문제를 단계적으로 해결해 나가는 과정에서 종전에 찾아 둔 해를 다시 활용하는 것이 동적 계획법의 중요 절차

※메모이제이션

중복되는 계산 결과를 저장하여 이전에 계산한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용

 

이미 1학기에 푼 백준 문제와 자료 구조 수업에서 배웠기 때문에 개념은 이정도로 간단히 정리하고 코드를 짜보았다.

dp = [[[0]*21 for _ in range(21)] for _ in range(21)]

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    if dp[a][b][c]:
        return dp[a][b][c]

    if a < b < c:
        dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return dp[a][b][c]

    else:
        dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
        return dp[a][b][c]

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break

    print(f"w({a}, {b}, {c}) = {w(a, b, c)}")

주어진 입력값 a, b, c에 따라 함수를 재귀적으로 호출하고 그 결과를 메모이제이션 기법을 이용해 저장하는 코드이다. 

dp = [[[0]*21 for _ in range(21)] for _ in range(21)]

3차원 리스트 dp를 선언하여 메모이제이션을 위한 테이블을 준비한다. a, b, c가 최대 20일 때까지 값을 저장하는데, 인덱스 0부터 20까지 사용하기 때문에 크기는 21로 설정한다.

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

주어진 조건에 따라 함수의 반환값을 결정한다.

    if dp[a][b][c]:
        return dp[a][b][c]

만약 dp[a][b][c]가 이미 계산되어 있으면 그 값을 바로 반환하여 재귀 호출을 방지한다.

    if a < b < c:
        dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return dp[a][b][c]

    else:
        dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
        return dp[a][b][c]

 

• a < b < c인 경우와 그렇지 않은 경우로 나누어 다른 규칙을 적용
  • a < b < c일 때는 3개의 재귀 호출 결과를 더하고 빼서 새로운 값을 만듦
  • 그렇지 않은 경우는 다른 방식으로 4개의 재귀 호출 결과를 조합하여 값을 계산
• 계산된 결과는 dp[a][b][c]에 저장되고, 저장된 값이 반환

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break

    print(f"w({a}, {b}, {c}) = {w(a, b, c)}")

 

 

 

• 입력값이 -1, -1, -1이면 프로그램이 종료
• 그렇지 않으면 w(a, b, c) 함수를 호출하여 그 결과를 출력