[JAVA] BOJ(백준) - 신나는 함수 실행 - 9184

문제 내용

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

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

제한

• -50 ≤ a, b, c ≤ 50

 

---

문제 접근 방법

우선 DP관련 문제를 바로전 피보나치 문제를 풀었을때 dp배열을 생성해 풀어냈으므로 이문제도 마찬가지 일거라 생각하고 접근했다.

 

사람들이 말하는 메모제이션..?은 쉽게 말해 그냥 DP배열 생성후 반복될 값들 계산후 저장해놓으면서 반복될시에 다시 계산하지 않고 DP배열에 꺼내 쓰는 것이다.

 

처음엔 어떤 규칙이 있지않을까 하고 w함수를 만들어서 여러가지 숫자를 넣으며 테스트 해봤는데.. 숫자가 같을때와 증가할때를 제외하고는 규칙이 있는건지 없는건지 모르겠다.

 

그래서 그냥 주어진 함수식을 사용해 풀어냈는데 풀이는 간단하다.

 

--

1. 3차원 DP 배열 생성

• a, b, c 세가지 변수에 따른 값이 필요하므로 3차원으로 생성

2. DP 배열의 크기는 21로한다.

• 21로 하는 이유는 a,b,c, 중 하나라도 20을 초과한다면 21부터는 무조건 a,b,c 는 20으로 바뀌면서 w함수를 재귀호출 하고, 0이하의 숫자로 a,b,c중 하나라도 있으면 return 값을 1로 반환하기 때문에 실질적으로 필요한 크기는 0~20까지인 크기로해주면 된다.

3. a, b, c 가 모두 -1이 나오지 않는이상 무한 루프로 돈다.

4. 문제에서 주어진 w함수 return값을 dp배열로 해준다.

5. 문제에서 요구한 출력값대로 출력해준다.

--

 

3~4번을 반복하고 루프 탈출한뒤 5번을 해주면 답이된다.

 

참고로 출력값 정확하게 입력하길 바란다... 콘마 다음에 띄어쓰기를 안해서 계속 틀렸다.. ㅠ

아무튼 풀이를 보자.

 

---

풀이

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

public class Main {
	static Integer[][][] dp = new Integer[21][21][21]; //dp 배열
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		
		int a = 0;
		int b = 0;
		int c = 0;
		
		dp[a][b][c] = 1; //dp의 초기값을 몇가지 써놨지만 의미가 거의없다..
		dp[1][1][1] = 2; //안써도됨.
		dp[1][2][4] = 2;
		dp[2][3][5] = 4;
		
		while(true) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			if(a==-1 && b==-1 && c==-1) {//a,b,c 모두 -1이면 탈출
				break;
			}
			//sb에 계속 문자 추가
			sb.append("w("+a+", "+b+", "+c+") = "+w(a, b, c)).append("\n");
		}
		//탈출후 출력
		System.out.println(sb.toString());
	}
	
	public static int w(int a, int b, int c) {
		//첫번째 if문은 이미 계산돼있는 경우 바로 dp[a][b][c] 를 반환해준다. 
		//dp배열은 index가 0~20까지라 a,b,c는 무조건 0~20 사이 숫자여야함.
		if(0<=a && 0<=b && 0<=c && a<=20 && b<=20 && c<=20) {
			if(dp[a][b][c]!=null) {
				return dp[a][b][c];
			}
		}
		if(a<=0 || b<=0 || c<=0) {
			return 1;
		}
		
		//아래부턴 dp배열에 주어진 함수식 값을 할당해줘서 값을 저장하고 리턴한다.
		if(a>20 || b>20 || c>20) {
			return dp[20][20][20] = w(20,20,20);
		}
		if(a<b && b<c) {
			return dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a,b-1,c);
		}
		return 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);
	}
}

 

---

마치며

DP관련 문제를 두번째로 푸는건데 쉬운 문제지만 혼자서 풀어냈다는 것에 뿌듯함을 느끼게 해준 문제이다.

다른문제도 풀수있기를!!!