[백준][JAVA알고리즘]9184번 풀이(신나는 함수 실행) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 9184번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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)를 출력한다.

제한

시간제한 : 1초
-50 ≤ a, b, c ≤ 50

입력 예시

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-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

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	static int[][][] me = new int[21][21][21];
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			if(a==-1 &&b==-1 &&c==-1)
				break;
			
			int n = 0;
			n +=w_function(a,b,c);
			
			sb.append("w(").append(a).append(", ")
			.append(b).append(", ").append(c)
			.append(") = ").append(n).append("\n");
		}
		
		
		System.out.println(sb);
		
}
	public static int w_function(int a, int b, int c) {
		
		if(a>=0&& a<=20&&b>=0&& b<=20&&c>=0&& c<=20&&me[a][b][c]!=0)
			return me[a][b][c];
			
		if(a <= 0 || b<=0 || c<=0) 
			return 1;
		
		if (a>20 || b>20 || c>20)
			return me[20][20][20]=w_function(20, 20, 20);
		
		if (a<b&&b<c)
			return  me[a][b][c]=w_function(a, b, c-1) + w_function(a, b-1, c-1) - w_function(a, b-1, c);
		
		
		return me[a][b][c]=w_function(a-1, b, c) + w_function(a-1, b-1, c) + 
					w_function(a-1, b, c-1) - w_function(a-1, b-1, c-1);
	}
}

이번 신나는 함수 실행 알고리즘은 함수가 굉장히 길어 보이지만 실상 가장 중요한 점은 바로 메모이제이션 기법을 사용하는 것입니다. 물론 저도 처음에 메모이제이션이 무엇인지 잘 몰랐었으며, 역시 이문제도 답은 나왔지만, 제한 시간 때문에 성공하지 못하였습니다. 그러나 다른 성공코드를 분석하여 메모이제이션을 알아보았고 이제 STEP을 따라가며 하나하나 이해해 보도록 하겠습니다~!

---

알고리즘 흐름도

입력받기 -> 세 개의 수가 -1인지 판단하기 -> 아닐 시 W_FUNCTION 사용하여 값 도출하기 -> 출력하기

---

STEP1 메모이제이션이란?

 메모이제이션은 동일한 계산을 반복할 때 계산한 값을 미리 변수에 저장함으로써 동일한 계산이 반복 수행하는 것을 줄여주어 빠르게 프로그래밍하는 기법을 말합니다.

 

뭐 아주 쉽게 말하자면, 반복문, 재귀 등을 이용할 때 배열이나 컬렉션에 저장해둠으로 써 반복의 횟수를 줄이는 방법입니다. 더더 쉽게 말하자면 그냥 반복문, 재귀를 일반적인 방법보다 빠르게 하는 기법이라고 생각하시면 됩니다!

---

STEP2 세 개의 수 -1인지 판단하기

사실 이거는 아주 쉽죠 아래처럼 if문 하나만 넣어주면 끝

while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			if(a==-1 &&b==-1 &&c==-1)
				break;
			
		}

---

STEP 3 메모이제이션을 활용한 재귀 방법

 여기가 바로 핵심입니다. 우선 메모이제이션을 넣기 전에 저희가 무슨 수를 얻어야 하는지 알아야 합니다. 결과론 적으로 출력 예시를 보면 w(1, 1, 1) = 2 이런 형식입니다. 여기에서 판단하면 저희가 구해야 하는 수는 바로 2입니다.

 

그렇게 되면 저희는 숫자 n만 얻으면 된다는 것이지요 아래처럼 말이죠.

		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			if(a==-1 &&b==-1 &&c==-1)
				break;
			
			int n = 0;
			n +=w_function(a,b,c);
			
			sb.append("w(").append(a).append(", ")
			.append(b).append(", ").append(c)
			.append(") = ").append(n).append("\n");
		}

여기서 w_function은 문제에서 주어시다시피 w(a, b, c) 재귀 함수를 사용한 것입니다. 이름은 달리해도 되고요

 

이제 핵심인 w_function에 대해 알아보겠습니다.

	public static int w_function(int a, int b, int c) {
		
		if(a>=0&& a<=20&&b>=0&& b<=20&&c>=0&& c<=20&&me[a][b][c]!=0)
			return me[a][b][c];
			
		if(a <= 0 || b<=0 || c<=0) 
			return 1;
		
		if (a>20 || b>20 || c>20)
			return me[20][20][20]=w_function(20, 20, 20);
		
		if (a<b&&b<c)
			return  me[a][b][c]=w_function(a, b, c-1) + w_function(a, b-1, c-1) - w_function(a, b-1, c);
		
		
		return me[a][b][c]=w_function(a-1, b, c) + w_function(a-1, b-1, c) + 
					w_function(a-1, b, c-1) - w_function(a-1, b-1, c-1);
	}

문제에서 주어진 w재귀 함수를 잘 이해하시면 됩니다. 만약 a b c가 0보다 작은 수가 있다면 그냥 1을 반환합니다. 2번째 if문은 쉽게 구현할 수 있죠. 나머지는 갑자기 me [][][] 이런 배열이 나오게 되었죠? 이게 바로 저희가 계산한 값을 넣어주는 변수의 역할을 하는 메모이제이션의 핵심 기능입니다.

 

함수를 차례 별로 해석해보도록 하죠

 

1번째 if문

 1번 if문을 이해하기 전에 2, 3번 if문 해설부터 보고 오세요!

1번의 경우 바로 메모이제이션의 핵심기능입니다. 만약에 저희가 저장한 값이 0이 들어가 있지 않다면, 즉 어떠한 값이 들어가 있다면, 이미 계산이 된 문제라는 의미입니다. 여기서 앞서 a, b, c의 조건들은 바로 20을 넘어가거나 0보다 작은 값들이 있는지를 판단해 주어야 합니다. 왜냐하면 2번째, 3번째 if문 보다 앞에 작성해 줌으로써 해당 조건들이 걸러지지 않기 때문입니다.

(그런데 왜 먼저 쓰느냐! 바로 메모이제이션 기법을 활용해 반복 횟수를 줄이기 위해서이죠. 이미 계산된 값이라면 굳이 또 재귀를 돌려 계산하지 않아도 되기 때문이죠)

 

2번째 if문

 2번 if문은 쉽습니다. 문제에서 주어진 것처럼 a, b, c에 0보다 작은 수가 있으면 1을 반환해줍니다.

 

3번째 if문

 3번째 if문의 경우 20보다 큰 수가 a, b, c에 있다면 문제에서는 w(20, 20, 20)을 반환하라고 하죠. 이 말은 즉 20보다 큰 수는 그냥 w(20,20,20)에 있는 수를 넣어주라는 것입니다. 쉽게 말해서 아무리 큰 수라도 20을 넘어가면 w(20,20,20)을 반환해 주면 됩니다. 

앞서 me [][][]에는 저희가 계산한 값을 저장한다고 되어있죠. 즉, 한계치인 me [20][20][20]의 값에 w(20, 20, 20)을 넣어주면 끝!

 

4번째 if문

이것 또한 문제에서 제시되어있듯이 해당 재귀를 저희가 원하는 me [a][b][c]에 넣어주면 끝!

 

마지막 return

아무 if문도 안 걸리면 문제에서 나와있듯이 반환해주는 코드!

---

step4 예시로 메모이제이션을 활용한 재귀 방법 이해하기

아직도 이해가 안 가실 수도 있습니다. 그러면 역시 간단하게 예시로 보여드리면 간단히 이해가 가실 겁니다. 우리가 사용할 예시는 바로 2 2 2 값이 들어왔을 때를 보여드릴게요

 

a = 2

b = 2

c = 2

 

w_function 함수에 인자가 들어가게 됩니다

 

자 이게 만약 처음 계산하는 값이라면, 1번 if문에는 걸리지 않습니다.

2, 3, 4번 if문에 걸리지 않게 되죠. 그러면 결국 마지막 return의 코드가 실행되게 됩니다.

 

return me [2][2][2] = w(1,2,2) + w(1,1,2)+w(1,2,1)-w(1,1,1)의 값이 들어가겠죠?

또 한 번 생각합니다.

 w(1,2,2) -> 1,2,3,4에 걸리지 않습니다. 

return me [1][2][2] = w(0,2,2) + w(0,1,2) + w(0,2,1) - w(0,1,1)

이런 식으로 들어가게 됩니다. 그러면 결국 이 4개의 함수는 2번째 함수에 걸리게 됩니다.

2번째 if문에 걸리게 되면 1이 반환되게 되어있죠.

그러면 me [1][2][2] = 1 + 1 + 1 - 1 = 2

2의 값이 들어가게 되죠.

다시 w(1,2,2)로 돌아가면 해당 함수에서 반환되는 수는 2가 된다는 의미가 되죠.

그렇다면

me [2][2][2] = 2 + w(1,1,2)+w(1,2,1)-w(1,1,1)의 식이 완성이 되죠 ㅎㅎ

 

쉽죠? 이런 식으로 나머지 w를 곰곰이 생각해본다면, 모두 마지막 return에 걸리며 w(1,2,2)처럼 모두 2를 반환하게 됩니다.

 

그렇다면 me [2][2][2] = 2 + 2 + 2 - 2 = 4 즉 저희가 원했던 결과로 4를 반환해 주게 되죠.

 

여기서! 그렇다면 다음에 만약에 a b c가 (1,2,2), (1,1,2), (1,2,1), (1,1,1)의 값이 들어오게 되면, 이미 me [][][]라는 3차원 배열에 값이 저장되어 있겠죠? 그렇다면 해당 2 2 2를 넣어준 다음에 해당 숫자들을 넣어준다면, 바로 첫 번째 if문에 걸리게 되어 재귀의 숫자를 줄여 더 빠르게 출력이 되는 것이죠.

 

이렇게 재귀의 반복 숫자를 줄여주는 것이 결론적으로 메모 이제이 션 기법이고 동적 계획법 문제에 자주 등장한답니다.