[백준/BOJ] 9184번 신나는 함수 실행 (C/C++)

백준 온라인 저지(BOJ) 9184번 신나는 함수 실행

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

9184번: 신나는 함수 실행

* 사용언어 : C언어, C++

 

1. 문제

문제에 주어진 w(a, b, c)를 구현하여 출력하는 프로그램을 작성

 

2. 풀이

문제에 w(a, b, c) 함수가 주어져있지만 그 방식 그대로 구현하면 시간 초과가 발생합니다.

시간 초과가 발생하지 않도록 불필요한 반복을 줄이려면 동적 계획법을 사용하면 됩니다.

 

동적 계획법은 용어 자체가 직관적이지 않은데, 기억하며 풀기(memoization)로 바꾸어 생각하면 보다 이해가 쉽습니다.

메모이제이션은 동일한 계산을 반복해야 할 때 이전에 계산한 값을 메모리에 저장하여 활용하는 기법입니다.

동적 계획법을 활용하면 메모이제이션을 활용하기 때문에 수행 시간을 큰 폭으로 줄일 수 있습니다.

(cf. 동적 계획법과 메모이제이션은 동의어가 아닙니다. 메모이제이션이 더욱 넓은 범위의 단어입니다.)

 

우선 dp[101][101][101]이라는 배열을 선언해두고 w(a, b, c)를 계산할 때마다 dp[a][b][c]에 값이 있는지를 확인합니다.

값이 있으면 그대로 return하고, 없으면 주어진대로 w를 계산하여 dp[a][b][c]에 저장한 뒤 그 값을 return 하면 됩니다.

 

a, b, c 값은 반복 횟수만 정하기 때문에 (-50, 50)의 범위에 +50을 해서 (0, 100)으로 보고 풀었습니다.

그 외 풀이는 단순하니 아래 코드로 설명 대체하겠습니다.

 

 

사실 동적 계획법을 학습하면서 알고리즘을 코드로 구현할 수 있게 되는 것 자체는 별로 의미가 없습니다.

하지만 추후 구동 시간을 줄여야하는 문제에서 활용할 만한 기법을 익힌다는 점은 상당히 큰 의미가 있는 것 같습니다.

예를 들어 특정 변수를 반복해서 연산해야 한다면 미리 한 번 해서 저장해둔 후 가져다 쓰거나

LUT(Look Up Table)을 선언해두고 처음 한 번만 계산한 후 계속 가져다가 쓰는 방식으로 활용할 수 있습니다.

 

dp 뿐 아니라 모든 알고리즘이 문제 해결을 위한 방법론을 배우는 것이니

원리를 이해한 후 반복 숙달하면서 방법론을 익혀두면 다양한 형태로 활용할 수 있습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
9184_신나는 함수 실행
5140KB	12ms
*/
#include <cstdio>

const int LM = 101;
int dp[LM][LM][LM], a, b, c;

int w(int a, int b, int c) {
	if (dp[a][b][c] == 0) {
		if (a <= 50 || b <= 50 || c <= 50) dp[a][b][c] = 1;
		else if (a > 70 || b > 70 || c > 70) dp[a][b][c] = w(70, 70, 70);
		else if (a < b && b < c) dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
		else dp[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 dp[a][b][c];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	while (1) {
		scanf("%d %d %d", &a, &b, &c);
		if (a == -1 && b == -1 && c == -1) break;
		printf("w(%d, %d, %d) = %d\n", a, b, c, w(a + 50, b + 50, c + 50));
	}
	return 0;
}