신나는 함수 실행
면접 대비시간 제한1초메모리 제한128 MB
메모이제이션을 사용해 재귀 함수 w(a, b, c)를 각 질의마다 계산하고 -1 -1 -1이 나오면 종료합니다.
문제
재귀 호출만 생각하면 신이 난다! 아닌가요?
정수 세 개를 받는 재귀 함수 w(a, b, c)를 다음과 같이 정의한다.
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
정의를 그대로 코드로 옮기기는 쉽다. 문제는 속도다. 같은 인자를 몇 번이고 다시 계산하기 때문에 a = 15, b = 15, c = 15 정도만 되어도 답이 나오지 않는다.
a, b, c가 주어지면 w(a, b, c)를 계산해서 출력하는 프로그램을 작성하시오.
입력
입력은 여러 줄로 이루어진다. 각 줄에는 정수 a, b, c가 공백 하나로 구분되어 주어진다.
마지막 줄은 -1 -1 -1이고, 이 줄은 계산하지 않는다. 세 값이 모두 -1인 줄은 마지막 줄뿐이다.
출력
입력에 주어진 각 줄마다 한 줄씩 w(a, b, c) = 결과 형식으로 출력한다. 괄호 안에는 입력에 주어진 세 정수를 그대로 쓰고, 쉼표 뒤와 등호 양옆에 공백을 하나씩 넣는다.
마지막 줄 -1 -1 -1에 대해서는 아무것도 출력하지 않는다.