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

걸린 시간: 20m53s

문제

다음과 같은 재귀함수 w(a, b, c)가 있다.

1if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
2    1
3
4if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
5    w(20, 20, 20)
6
7if a < b and b < c, then w(a, b, c) returns:
8    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
9
10otherwise it returns:
11    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, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

문제 접근 방법

풀이

1#include <bits/stdc++.h>
2using namespace std;
3
4#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
5#define endl '\n'
6#define s(a,b,c) s[(a)][(b)][(c)]
7
8int s[21][21][21];
9
10int w(int a, int b, int c) {
11  if (a<=0 || b<=0 || c<=0) return 1;
12  if (a>20 || b>20 || c>20) return w(20,20,20);
13  if (a<b && b<c) {
14    if(s(a,b,c-1) == 0) s(a,b,c-1) = w(a,b,c-1);
15    if(s(a,b-1,c-1) == 0) s(a,b-1,c-1) = w(a,b-1,c-1);
16    if(s(a,b-1,c) == 0) s(a,b-1,c) = w(a,b-1,c);
17    return s(a,b,c-1) + s(a,b-1,c-1) - s(a,b-1,c);
18  } else {
19    if(s(a-1,b,c) == 0) s(a-1,b,c) = w(a-1, b, c);
20    if(s(a-1,b-1,c) == 0) s(a-1,b-1,c) = w(a-1, b-1, c);
21    if(s(a-1,b,c-1) == 0) s(a-1,b,c-1) = w(a-1, b, c-1);
22    if(s(a-1,b-1,c-1) == 0) s(a-1,b-1,c-1) = w(a-1, b-1, c-1);
23    return s(a-1,b,c) + s(a-1,b-1,c) + s(a-1,b,c-1) - s(a-1,b-1,c-1);
24  }
25}
26
27int main(){
28  ios;
29  int a,b,c;
30  cin >> a >> b >> c;
31  while(1) {
32    if(a == -1 && b == -1 && c == -1) break;
33    printf("w(%d, %d, %d) = %d\n", a, b, c, w(a,b,c));
34    cin >> a >> b >> c;
35  }
36  return 0;
37}

리팩토링

코드 제출 후, 다른 코드를 살펴보니 훨씬 간단히 가능했다. 나는 하나하나 계산 과정을 저장했지만 그럴 필요없이, 최초의 (a,b,c) 위치에 해당 계산 값을 보존해두면 되었다.

1int s[21][21][21];
2
3int w(int a, int b, int c) {
4  if (a<=0 || b<=0 || c<=0) return 1;
5  if (a>20 || b>20 || c>20) return w(20,20,20);
6  if(s(a,b,c)) return s(a,b,c);
7
8  if (a<b && b<c) {
9    return s(a,b,c) = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);
10  } else {
11    return s(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);
12  }
13}

시간 복잡도

• 최종 시간 복잡도: 최대 약 3천번 계산하는 건 파악이 됐지만 어떻게 계산해야 되지...

공간 복잡도

• 최종 공간 복잡도: O(ABC), where A, B, and C are <= 20