코테연습 - 4단 고음

문제

4단 고음

사고

그냥 어렵다. 그래서 어떻게 풀어야 하는지 구글링 좀 했다.

dfs를 할건데 n부터 1이 될 수 있는지 거꾸로 생각할 거다.
*은 3으로 나누고 +은 1을 뺄 거다.

유효한 문자열의 특징이 있다.

• 무조건 끝이 ++다. 이해가 안되겠으면 직접 해봐라.
• 뒤에서부터 i번째로 *이 나오려면 +가 최소 2*i개 있어야한다.

두번째가 이해가 안된다면 반대로 생각해보자.
뒤에서부터 +가 3개 등장했고 *가 한 번 등장했다고 예시를 들어보자. 이 상황에서 한번 더 *을 등장시킬 수 있는 조합은 없다.

[......]*+*++ (X)
[......]+**++ (X)

절대 안나온다.

풀이

import java.util.*;

// 존나 어렵노 시발

class Solution {
    int res = 0;
    
    public int solution(int n) {
        int starCnt = (int)(Math.log(n) / Math.log(3));
        dfs(n-2, starCnt,0,2);
        return res;
    }
    
    void dfs(int currentNum, final int totalStar, int usedStar, int usedCross){
        if(currentNum == 1 && usedStar == totalStar && usedCross == 2*totalStar){
            res++;
            return;
        }
        
        if(2*(usedStar+1) <= usedCross && currentNum % 3 == 0 && currentNum > 2){
            dfs(currentNum/3, totalStar, usedStar+1, usedCross);
        }
        if(usedCross + 1 <= totalStar * 2){
            dfs(currentNum -1, totalStar, usedStar, usedCross + 1);
        }
    }
}