[9184] 신나는 함수 실행

---

내가 스스로 짜긴 했는데 완전 야매 느낌이라 다른 사람들의 풀이를 보고 고쳤다. ㅜㅜ

 

재귀 함수를 쓰면 시간 초과가 뜨겠지! 라는 생각에 사로잡혀 그냥 for문을 3번 돌렸다

결론적으로 맞았는데, 예제가 없었다면 틀렸을 것이다. 아주아주 부끄러운 풀이다.

#include <iostream>
#include <cmath>
using namespace std;

int a, b, c, aa, bb, cc;
int w[101][101][101];

int change(int x) {
	// x가 음수 : 1~50 index에 저장
	// x가 양수 : 51~100 index에 저장
	if (x < 0) {
		return abs(x);
	}
	else if (x > 0) {
		return x + 50;
	}
}

void f() {	
	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			for (int k = 0; k <= 100; k++) {
				if (i <= 50 || j <= 50 || k <= 50) { // a,b,c 중 하나라도 0보다 작다면
					w[i][j][k] = 1;
					continue;
				}
				if (i > 70 || j > 70 || k > 70) { // a, b, c 중 하나라도 20보다 크면
					w[i][j][k] = 1048576; // 제일 부끄러움 
					continue;
				}
				
				if (i < j && j < k) {
					w[i][j][k]=w[i][j][k-1]+ w[i][j - 1][k - 1] - w[i][j - 1][k];
				}
				else {
					w[i][j][k] = w[i - 1][j][k] + w[i - 1][j - 1][k] + w[i - 1][j][k - 1] - w[i - 1][j - 1][k - 1];

				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	f();
	while (1) {
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1) break;
		aa = change(a);
		bb = change(b);
		cc = change(c);

		printf("w(%d, %d, %d) = %d\n", a, b, c, w[aa][bb][cc]);
	}

}

저렇게 for문을 3번 돌리다 보면 w[20][20][20]의 값을 알지 못한다. 그래서 예제에 있던 값을 넣어줘서 풀었더니 맞았습니다가 떴다. 굉장히 무식한 풀이다. 풀이라고 인정할 수도 없다.

내가 생각해도 너무 찝찝한 부분이 많아 다른 사람들의 풀이를 보았다.

 

일단 DP 설명부터..

Dynamic Programming :  동적 프로그래밍. 문제들을 다시 계산하지 않고 큰 문제를 작은 문제로 분할한다. 작은 문제의 답을 큰 문제를 풀 때 재사용함.

보통 재귀, 배열을 이용하여 문제를 푼다.

 

3개의 숫자들 중 하나라도 0보다 작으면 1을 반환하고, 하나라도 20보다 크면 W(20,20,20)을 호출하는 함수 W을 작성하였다.

#include <iostream>
using namespace std;

int a, b, c;
int w[21][21][21];

int W(int a, int b, int c) {
	if (a <= 0 || b <= 0 || c <= 0) {
		return 1; // a,b,c 중 하나라도 0보다 작으면 1
	}
	if (a > 20 || b > 20 || c > 20) { 
		return W(20, 20, 20); // a,b,c 중 하나라도 20보다 크면 W(20,20,20) 호출
	}

	if (w[a][b][c])return w[a][b][c]; // 값이 채워져있다면 바로 반환. 이 코드 없으면 시간 초과. dp

	if (a < b && b < c) { // a<b<c라면
		w[a][b][c] = W(a, b, c - 1) + W(a, b - 1, c - 1) - W(a, b - 1, c); // 아직 안채워져있다면 재귀를 이용하여 더 아래의 값들을 불러옴
	}
	else {
		w[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 w[a][b][c];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (1) {
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1) break;

		printf("w(%d, %d, %d) = %d\n", a, b, c, W(a,b,c));
	}

}

저 중간에 있는 if(w[a][b][c])문이 중요하다. 저것이 없으면 시간초과가 뜬다. 중복된 것은 굳이 다시 계산하지 않고 값을 반환하고 끝내야 한다. 저게 DP라고 볼 수 있다!

 

시간 단축에 대해 더 고민해보는 계기가 되었다..