[ C++ ] #9184 신나는 함수 실행

9184

 

정의해준 재귀함수를 분석해보겠다.

인자로 a,b,c 가 들어오고 이 값에 따라 재귀호출을 하는 것 같다.

 

1. a,b,c 중 하나라도 0이하가 되면 1을 리턴한다.
2. a,b,c 중 하나라도 20이상이 되면 a,b,c에 20을 넣고 재귀호출한다.
3. a<b<c 가 되면 w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) 를 호출한다.
4. 모두 아니라면 w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)를 호출한다.

문제에 나와있는것 처럼 구현하는것은 쉬울 것같다.

하지만 제한시간에 걸릴 것 같다.

 

---

함수를 잘 뜯어보니까 같은 함수가 여러번 실행되는 것 같다는 생각이 들었다. 

이미 계산이 되었던 함수의 값은 저장해놓고 재활용하면 

계산횟수를 훨씬 줄일 수 있을 것 같다.

 

함수의 입력값이 세개이므로 3차원 배열에 값을 저장해놓으면 어떨까 생각했다.

 

---

됐다..!! 

 

함수에 들어갔을 때 배열을 확인하고 배열에 값이 있다면 그 값을 return 해줌으로써 계산횟수를 줄여줬다

배열에 없다면 조건을 거쳐 값이 생성되고 값이 리턴되기 전에 각 배열에 넣어주었다.

 

내가 만난 오류는 다음과같다.

1. 런타임오류 : 배열크기 실수

배열을 50*50*50 로 만들어서 배열은 [49][49][49]까지 사용가능한데,

나는 실제 숫자를 배열 자리로 똑같이 만들어서 w(50,50,50)을 넣었을 때 [50][50][50] 에 들어가서 오류가 났다.

→ 배열을 하나 늘려주었다.

 

2. 런타임오류 : 음수 처리

음수가 나왔을 때 1을 리턴하는 과정이 배열에 넣는거보다 뒤에있어서

배열에 있을 때 음수가 들어가 런타임 오류가 났다

→음수가 나왔을 때 1를 리턴해주는 코드를 함수 최상단에 넣어주었다. 

 

#include <iostream>

using namespace std;
int abc[51][51][51];

int w(int a, int b, int c) {

	if (a <= 0 || b <= 0 || c <= 0) return 1;  //음수처리

	if (abc[a][b][c]) {  //배열에 이미 계산된 값이 있다면 리턴
		return abc[a][b][c];
	}

	else if (a > 20 || b > 20 || c > 20) {
		int x= w(20, 20, 20);
		abc[a][b][c] = x;
		return x;
	}
	else if (a <b && b < c ) {
		int x= w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
		abc[a][b][c] = x;
		return x;
	}
	else {
		int x = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
		abc[a][b][c] = x;
		return x;
	}
}

int main() {

	int a, b, c;

	while (1) {

		cin >> a >> b >> c;
		if (a == -1&&b==-1&&c==-1) break;  //종료조건

		cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a, b, c)<<endl;

	}
}