[백준] 9184번 : 신나는 함수 실행

9184번: 신나는 함수 실행

# 입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

 

# 출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

 

# 제한

• -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

---

전형적인 동적 프로그래밍(Dynamic Programming) 방식의 문제이다. 문제 자체에 '동적 프로그래밍'으로 해결하시오. 라고 써놓은 정도이다. 반복적인 호출이 여러 번 이루어져야 한다면, DP를 이용하여 배열이나 표 등 다른 저장공간에 값을 저장하며 풀어보자.

 

먼저 w(a, b, c)는 다음과 같다. 

/* -50 <= a,b,c <= 50 */
static int w(int a, int b, int c){

  if(a <= 0 || b <= 0 || c <= 0)
  	return 1;

  else if(a > 20 && b > 20 && c > 20) 
 	return w(20, 20, 20);

  else if(a < b && b < c)
  	return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);

  else
 	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);
}

1) a, b, c 중 하나라도 0 이하인 경우 :  return 1

2) a, b, c 중 하나라도 20 이상인 경우 : return w(20, 20, 20)

3) a < b < c 인 경우 : w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

4) 나머지 경우 : w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

 

처음 문제를 접하고 여러 방면으로 접근해보았다.

 

# 1차원 배열에 w(a, b, c) 값 저장하기 (X)

0 < a, b, c < 21 범위가 아닌 값들은 (예: {0, 0, 0}, {21, 50, 30}, {-1, 20, -30}...) 정해진 하나의 값을 반환한다. 따라서 abc 각 자리에 올 수 있는 값은 1~20까지 총 20개이다. 그렇다면 a에 20개 b에 20개 c에 20개 이므로 경우의 수는 20*20*20이다. 상당히 큰 값이다. 여기에 +2를 해야한다. 왜냐하면 a,b,c가 0일 때, a,b,c가 20 초과일 때 값을 넣을 자리가 필요하기 때문이다. 벌써부터 머리가 복잡하다. 그래도 꿋꿋하게 진행해보았다.

 

a의 자리의 값이 하나 줄어들 때마다 index는 몇이나 줄어들까? 20*20 만큼 줄어들 것이다.

b는? 20만큼 줄어들 것이다.

c는 1만큼 줄어들 것이다.

 

예를 들어, w(2, 1, 1)의 값을 갖는 배열의 인덱스가 401일 때, w(a-1, b, c)의 값을 갖는 배열의 인덱스는 1이다.

그럼 w(20, 19, 20)의 인덱스는...? 할 때쯤 내가 너무 어렵게 생각하고 있는 것이 아닌가 고민했다. 그냥 3차원 배열을 만들면 더 쉬울텐데.. 해서 다 갈아엎어서 새로 코드를 작성했다.

 

# 3차원 배열에 w(a, b, c) 값 저장하기 (O)

전역 변수로 3차원 배열 int arr[][][] = new int[21][21][21]을 만들어서 저장하기로 했다. arr[a][b][c]의 값을 반환 받는다. 배열의 크기가 20이여도 상관없으나, a b c의 값과 배열의 인덱스를 일치시켜주기 위해 21로 지정했다. (a[1][1][1]이 실제로 a[0][0][0]을 담당할 것이다.)

 

문제에 주어진 w(a, b, c)를 조금 변형시켜보자. 계속 재귀호출을 하는 것이 아닌, 찾고자 하는 배열에 값이 들어있다면, 재귀호출을 하지말고 있는 값을 반환하라는 코드로...
(+ 인자로 받은 a, b, c를 범위에 맞게 조정시켜주는 작업도 필요하다)

static int[][][] arr = new int[21][21][21];

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

  if(a <= 0 || b <= 0 || c <= 0) //abc중 하나라도 0 이하? return 1;
  	return 1;
  if(a > 20 || b > 20 || c > 20) //abc중 하나라도 21 이상? abc 모두 20
  	a = b = c = 20;

  if(arr[a][b][c] != 0) //배열에 값이 있다면 값만 주세요.
  	return arr[a][b][c];

  if(a < b && b < c)
  	return arr[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
  else
  	return arr[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);
}

실제로 이 코드가 전부이다. main()에서는 그냥 a b c만 받아서 전달하고 결과만 출력해준다. 만약 a에 50이 들어왔다면 a=b=c=20으로 변경되어 맨 아래코드(w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1))가 실행될 것이다.역시 3차원 배열에 담기를 잘한 것 같다. 아까처럼 1차원 배열로 쭉 갔으면 아직도 인덱스를 신경쓰며 헤매고 있었을 것이다. 

 

# Whole Code </>

Java 11

import java.util.Scanner;

public class Main {

    static int[][][] arr = new int[21][21][21];

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

        if(a <= 0 || b <= 0 || c <= 0) //abc중 하나라도 0 이하? return 1;
            return 1;
        if(a > 20 || b > 20 || c > 20) //abc중 하나라도 21 이상? abc 모두 20
            a = b = c = 20;

        if(arr[a][b][c] != 0) return arr[a][b][c];

        if(a < b && b < c)
            return arr[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        else
            return arr[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);
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int a, b, c;

        while(true) {
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();

            if(a == -1 && b == -1 && c == -1) break;

            System.out.printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
        }
        sc.close();
    }
}

* 참고로 a = b = c = -1 일 때 반드시 종료되어야 하므로 중간에 break를 넣어주지 않으면 오답으로 판별된다.