1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.*;
class Solution {
    public int solution(int n) {
        /*
            n을 구성하는데 필요한 *와 +의 숫자를 먼저 구해야 한다.
            n은 3^(* 개수) 보다 크고 3^(* 개수 +1)보다 작아야 한다.
            즉 *의 개수는 log(n)/log3 이다. 
            +의 개수는 *의 개수의 2배이다.
        */ 

        // s= *의 개수
        int s=(int)(Math.log(n)/Math.log(3));
        /*
            n의 맨 뒤 두자리는 무조건 ++가 온다. 
            그 이후에 맨 뒤에 올 수 있는것은 + 또는 * 이다.
            맨 뒤의 +또는 *를 삭제해가며 n을 점차적으로 줄여나가보자. 
            이때 점차 줄어든 n을 k라 한다.

            k%3==0 이면, 맨 뒤의 *를 삭제하고 k/3을 구한다.
            k%3!=0 이면, 맨 뒤의 +를 삭제하고 k-1을 구한다. 

            이때, **++++++은 가능하지만, ++++++**은 불가능하다. 
            삭제된 *개수는 삭제된 +의 개수의 2배를 초과하면 안된다. 
            (*개수 *2 <= +개수)를 만족해야 한다.           
        */
        return run(n-2, s, s*2-2, 0, 2);
    }
    // s는 *의 수
    // p는 +의 수
    // cut_s는 줄어든 *의 수
    // cut_p는 줄어든 +의 수
    int run(int n, int s, int p, int cut_s, int cut_p){
        int a=0;
        int b=0;
        if(cut_s *2 >cut_p) // **++++++는 가능하지만 ++++++**은 불가능하도록 조건 구성
            return 0;
        if(n<3){
            return 0;
        }
        else if(n==3 && s==1 && p==0){
            return 1;
        }
        if(p>0){ // 맨 뒤에 p를 하나 지우고(p-1) n-1을 구한다. p를 하나 지웠기 때문에 cut_p는 1 증가한다.
            a=run(n-1, s, p-1, cut_s, cut_p+1);
        }
        if(n%3==0 && s>0){ // 맨 뒤에 *를 하나 지우고(s-1) n/3을 구한다. *를 하나 지웠기 때문에 cut_s는 1 증가한다.
            b=run(n/3, s-1, p, cut_s+1, cut_p);
        }
        return a+b;
    }
}