[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

  

 

---

• 문제

 

 

 

 

문제가 어려운 편은 아니다. 주어진 조건에 따라 함수를 그대로 옮겨적고 메모이제이션만 추가하면 된다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

문제를 설명하기는 모호한데.. 

일단 동적계획법의 특징은 대체로 재귀 + Memoization(메모이제이션) 이라는 것을 생각하면 된다.

 

 

위에서 설명한 조건에 따른 함수(재귀)호출은 코드로 보면 이렇다.

 

static int w(int a, int b, int c) { 
		
	if(a <= 0 || b <= 0 || c <= 0) {
		return 1;
	}
		
	if(a > 20 || b > 20 || c > 20) {
		return w(20, 20, 20);
	}
		
	if(a < b && b < c) {
		return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	}
	
	return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}

 

 

이렇게 w함수가 주어졌기 때문에 구현은 따로 풀이 할 필요가 없다.

 

 

그럼 이 부분을 동적계획법으로 풀어나가야 한다는 점이 가장 큰 문제일 것이다. 메모이제이션. 즉, 처음 방문하는 재귀라면 계산을 통해 얻은 값을 메모리에 저장(기록)하고, 이 후 재방문을 할 경우 다시 계산하는 것이 아닌 저장 된 값을 사용하라는 것이다.

 

이 문제에서는 a, b, c 라는 변수가 작용하는만큼 3차원 배열을 이용하여 풀이하면 되겠다.

 

즉, 다음과 같이 말이다.

static int dp[][][];	// 이미 배열이 생성되었다고 가정

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

	// 이미 계산되어 저장되어있는 경우 해당 값을 바로 반환 
	if(dp[a][b][c] != 0) {
		return dp[a][b][c];
	}
		
	if(a <= 0 || b <= 0 || c <= 0) {
		return 1;
	}

	/*
	 * a, b, c중 하나라도 20이 넘어가면 w(20, 20, 20)을 호출하기 때문에
	 * dp[20][20][20] 에 저장하고 반환하면 된다.
	 */
	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 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배열에 저장해두는 것과, 이미 저장된 경우만 추가해주면 대부분 완성이 된다.

나머지는 코드를 보면서 주석과 함께 살펴보도록 하자.

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

알고리즘은 크게 다를게 없고 입출력의 차이만 있을 것이다. 아래와 같이 3가지 입출력 방법을 통해 성능을 비교해보려 한다.

 

 

1. Scanner + System.out.printf

2. Scanner + StringBuilder

3. BufferedReader + StringBuilder 

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + printf]

 

import java.util.Scanner;

public class Main {

	/*
	 * 함수 w에서 a, b, c 중 20이 넘어가게 되면 w(20, 20, 20)을 호출하고,
	 * 0 이하일 경우는 1을 반환하기 때문에
	 * 각 배열의 크기가 21 (0~20)을 넘기지 않는다.
	 */
	static int[][][] dp = new int[21][21][21];
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);		
		
		while(true) {
			
			int a = in.nextInt();
			int b = in.nextInt();
			int c = in.nextInt();
			
			// -1 -1 -1 이 나오면 종료
			if (a == -1 && b == -1 && c == -1) {
				break;
			}
			
			System.out.printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
		}
		
	}
	
	static int w(int a, int b, int c) { 
		
		// a, b, c가 범위를 벗어나지 않으면서 메모이제이션이 되어있는 경우
		if(inRange(a, b, c) && dp[a][b][c] != 0) {
			return dp[a][b][c];
		}
		
		if(a <= 0 || b <= 0 || c <= 0) {
			return 1;
		}
		
		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);
	}
	
	/*
	 *  배열을 참조하려 할 때 a, b, c 중 하나라도 범위 밖의 수가
	 *  나올 수 있기 때문에 이를 체크를 해주기 위한 함수다.
	 */
	static boolean inRange(int a, int b, int c) {
		return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20; 
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

그리고 메소드를 하나 더 추가했다. 문제 조건을 잘 읽어보면 세 변수중 하나라도 0이하일 경우는 1, 20을 초과한 경우에는 w(20, 20, 20)을 호출한다. 결과적으로 실제 쓰이는 범위는 0~20까지밖에 안된다. 한마디로 dp[a][b][c] 에 대하여 각 차원에 대해 21개(0~20)의 공간만 생성해준 뒤 메모이제이션을 해주면 된다.

대신에 한 가지 조건이 붙는다면, 처음 w을 호출 할 때에는 음수 또는 20이 넘는 수가 입력 될 수도 있기 때문에 배열을 참조하고자 할 때 IndexOutOfBoundException 즉, 잘못된 참조가 이루어질 수 있기에 이를 체크하기 위한 메소드 inRange() 가 추가되었다.

 

 

 

 

 

---

- 방법 2 : [Scanner + StringBuilder]

 

 

 

 

위 방법에서는 printf로 매 번 출력을 했다. 이는 출력부분에서 효율이 떨어지기 때문에 StringBuilder로 묶어서 좀 더 개선을 한 방법이다.

 

 

import java.util.Scanner;

public class Main {

	/*
	 * 함수 w에서 a, b, c 중 20이 넘어가게 되면 w(20, 20, 20)을 호출하고,
	 * 0 이하일 경우는 1을 반환하기 때문에
	 * 각 배열의 크기가 21 (0~20)을 넘기지 않는다.
	 */
	static int[][][] dp = new int[21][21][21];
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		StringBuilder sb = new StringBuilder();
		
		
		while(true) {
			
			int a = in.nextInt();
			int b = in.nextInt();
			int c = in.nextInt();
			
			// -1 -1 -1 이 나오면 종료
			if (a == -1 && b == -1 && c == -1) {
				break;
			}
			
			sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(w(a ,b ,c)).append('\n');
			
		
		}
		
		System.out.println(sb);
	}
	
	static int w(int a, int b, int c) { 
		
		// a, b, c가 범위를 벗어나지 않으면서 메모이제이션이 되어있는 경우
		if(inRange(a, b, c) && dp[a][b][c] != 0) {
			return dp[a][b][c];
		}
		
		if(a <= 0 || b <= 0 || c <= 0) {
			return 1;
		}
		
		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);
	}
	
	/*
	 *  배열을 참조하려 할 때 a, b, c 중 하나라도 범위 밖의 수가
	 *  나올 수 있기 때문에 이를 체크를 해주기 위한 함수다.
	 */
	static boolean inRange(int a, int b, int c) {
		return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20; 
	}
}

 

 

 

알고리즘은 차이가 없어서 크게 어려울 것은 없을 것이다. 

 

 

 

 

---

- 방법 3 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 a, b, c를 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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

public class Main {

	/*
	 * 함수 w에서 a, b, c 중 20이 넘어가게 되면 w(20, 20, 20)을 호출하고,
	 * 0 이하일 경우는 1을 반환하기 때문에
	 * 각 배열의 크기가 21 (0~20)을 넘기지 않는다.
	 */
	static int[][][] dp = new int[21][21][21];
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		
		
		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());
			
			// -1 -1 -1 이 나오면 종료
			if (a == -1 && b == -1 && c == -1) {
				break;
			}
			
			sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(w(a ,b ,c)).append('\n');
			
		
		}
		
		System.out.println(sb);
	}
	
	static int w(int a, int b, int c) { 
		
		// a, b, c가 범위를 벗어나지 않으면서 메모이제이션이 되어있는 경우
		if(inRange(a, b, c) && dp[a][b][c] != 0) {
			return dp[a][b][c];
		}
		
		if(a <= 0 || b <= 0 || c <= 0) {
			return 1;
		}
		
		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);
	}
	
	/*
	 *  배열을 참조하려 할 때 a, b, c 중 하나라도 범위 밖의 수가
	 *  나올 수 있기 때문에 이를 체크를 해주기 위한 함수다.
	 */
	static boolean inRange(int a, int b, int c) {
		return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20; 
	}
}

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 24850920  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 24850916  -  방법 2 : Scanner + StringBuilder

채점 번호 : 24850913  -  방법 1 : Scanner + printf

 

 

입출력 방식에 따라 성능이 많이 차이나는 것을 볼 수 있다.

 

---

• 정리

 

2021.01.02 일 쯤 기점으로 동적계획법 1 카테고리 중 문제 하나가 새로 업데이트 된 문제다. 아마 동적계획법에 대해 많이 어려워 하기 때문에 함수는 이미 구현해놓고 가장 중요한 메모이제이션을 활용하는 법을 알 수 있도록 돕는 것에 아주 적절한 문제인 것 같다.

 

앞으로는 함수를 구현해야 할 텐데, 그리 어렵지 않다.

동적계획법 문제를 풀기위한 가장 기본 단계 3개만 알고있으면 된다.

 

1. 점화식 찾기 (동적계획법의 핵심은 반복되는 계산을 줄이는 것이기 때문에 대부분 점화식으로 표현이 가능하다.)

2. 점화식에서 반복되는 수식 확인하기 

3. 점화식을 재귀식으로 옮기면서 반복되는 수식은 메모리에 저장하기 (재귀 말고 반복문으로도 변환이 가능하지만, 일단은 재귀로 옮기는 연습부터 하는 것을 추천한다.)

 

위 3가지 과정을 거치면 대부분 완벽하게까진 아니더라도 동적계획법 방식으로 문제를 해결 할 수 있다.

 

만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.