230302 4단 고음

최종 결과값이 주어지고 규칙이 주어졌으므로 dfs를 이용해 역으로 가능한 조합을 재귀를 통해 찾아가는 방식을 사용함

private int answer;

public int solution1(int n) {
    answer = 0;
    dfs1(n, 0);
    return answer;
}

private void dfs1(int value, int cnt) {
    if (value < 1 || 2 * Math.log(value) / Math.log(3) < cnt)
        return;
    if (value == 3) {
        if (cnt == 2)
            answer++;
        return;
    }

    if (value % 3 == 0 && cnt >= 2) {
        dfs1(value / 3, cnt - 2);
    }
    dfs1(value - 1, cnt + 1);
}

public int solution2(int n) {
    return dfs2(n, 0);
}

private int dfs2(int value, int cnt) {
    if (value < 1 || 2 * Math.log(value) / Math.log(3) < cnt) {
        return 0;
    }
    if (value == 3) {
        return (cnt == 2) ? 1 : 0;
    }

    int result = 0;
    if (value % 3 == 0 && cnt >= 2) {
        result += dfs2(value / 3, cnt - 2);
    }
    result += dfs2(value - 1, cnt + 1);
    return result;
}