반응형
위에 있는 슈도 코드로 작성을 하게 될 경우, 입력 50 50 50에서 로컬 환경에서도 답안이 제 시간에 나오지 않았다. 그래서 이미 계산된 수식?은 생략할 수 있는 메모이제이션을 활용하기로 하였다.
풀이
더보기
# dp 테이블을 초기화합니다. 21x21x21 크기로 모든 값을 0으로 설정합니다.
# a, b, c의 최대값이 20이므로, 0~20까지의 인덱스를 사용하기 위해 21로 설정합니다.
dp = [[[0] * 21 for _ in range(21)] for _ in range(21)]
# w 함수를 정의합니다. 이 함수는 위 문제에서 주어진 조건에 따라 값을 계산합니다.
def w(a, b, c) :
# a, b, c 중 하나라도 0 이하일 경우 1을 반환합니다.
if a <= 0 or b <= 0 or c <= 0 :
return 1
# a, b, c 중 하나라도 20 초과일 경우 w(20, 20, 20)의 값을 반환합니다.
if a > 20 or b > 20 or c > 20 :
return w(20, 20, 20)
# dp[a][b][c]가 이미 계산되어 있다면, 그 값을 바로 반환하여 중복 계산을 방지합니다.
if dp[a][b][c] :
return dp[a][b][c]
# 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)
# 그 외의 경우에는 다른 공식을 사용하여 값을 계산합니다.
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 값을 입력받습니다.
a, b, c = map(int, input().split())
# 만약 입력받은 값이 모두 -1이라면 반복문을 종료합니다.
if a == b == c == -1 :
break
# 계산된 w 함수의 값을 출력합니다.
print(f"w({a}, {b}, {c}) = {w(a, b, c)}")
우선 while True 부분을 입력하였다.
a,b,c 를 입력받고 전부 -1 이면 입력을 그만 받도록 하였다. 그리고 함수 w 를 return 하는 입력부를 완성하였다
이후 w 함수를 정의하기 전에 동적 계획법을 활용할 배열을 하나 만들었다. 변수가 a b c 총 3가지 이기 때문에 3차원 배열을 만들었으며 20을 초과하면 20으로 리턴 받는 로직이 함수 내부에 있어서 각 변수마다 21개의 크기로 생성하였다.
일단 바로 리턴하는 함수를 먼저 정의를 하였다. 변수들 중 하나가 0 이하가 입력받으면 1을 리턴, 20을 초과하면 a,b,c =20 을 입력받아서 바로 리턴하였다.
나머지는 dp테이블에 각 값을 입력하였다. 그리고 이하 조건들은 문제에 나타나 있는 대로 잘 작성하면 문제는 해결된다.
이번 문제를 해결하면서 중요했던게 일단 수도 코드 대로 한 번 작성해보는 것이었다. 초보이기 때문에 그것을 어떻게 하면 다르게 표현할 수 있는지 생각해내는 단계가 아직은 도달하지 못하였다. 이번 문제는 재귀에 대해서 다시 한 번 생각해보고 재귀 + 동적 계획법을 이렇게도 활용 할 수 있는지를 확인할 수 있었다.
반응형