[프로그래머스] 4단 고음 (C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1831

아이디어1

DFS를 이용

뒤에서부터 +와 *을 차례로 세면서 적용

• *++ 순이기 때문에 +는 *의 2배 이상이어야 함
• 현재까지 +와 *x2의 차이 만큼 3으로 나눴을 때 1보다 작아지는지 확인

#include <cmath>

using namespace std;

void DFS(int num, int star, int plus, int& answer)
{
    if (num <= 1)
    {
    	// *과 +의 개수가 맞아야함
        if (plus == star * 2)
            answer++;
        return;
    }
    
    // + 2개마다 * 하나를 늘릴 수 있음
    if (plus >= (2 + star * 2) && (num % 3) == 0)
    {
        DFS(num / 3, star + 1, plus, answer);
    }
    
    // +와 *의 차이가 늘어나면 3으로 나눌 크기인지 확인
    if (num >= pow(3, (plus - 2 * star) / 2))
    {
        DFS(num - 1, star, plus + 1, answer);
    }
}

int solution(int n) {
    int answer = 0;
    
    DFS(n, 0, 0, answer);
    
    return answer;
}