[백준 알고리즘] 9184번 : 신나는 함수 실행, c++

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

c++로 백준 9184번 문제를 풀어보겠다.

 

 

 

 

 

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 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인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

제한

• -50 ≤ a, b, c ≤ 50

예제 입력 1 복사

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

예제 출력 1 복사

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

 

 

 

 

<문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

visual studio에선 원하는 대로 출력은 됐지만 입력값이 너무 클 땐 알고리즘이 복잡해 빨리 출력되지 않았고, 백준 사이트에선 '시간 초과'가 떴다.

 

 

최종적으로 작성한 코드는 다음과 같다.

1. 3차원의 새로운 배열을 선언한다.

2. 문제에 제시된 함수 w를 선언한다.

(주어진 함수의 형태는 그대로 가져오되, 한번 함수를 돌면 배열에 그 값을 저장하도록 한다.)

3. main 함수를 구현한다.

(while 반복문을 통해 a, b, c 값을 입력받고 함수 w에 a, b, c 값을 넣어 동작하도록 한다.)

 

 

 

 

이 문제를 통해 알게 된 점 :

주어진 함수의 형태를 사용하되, 새로운 배열을 사용해 계산을 덜 복잡하도록 만들어주는 것이 중요했다.