프로그래머스 Level 4 4단고음

4단고음 (프로그래머스 Level 4)

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

생각보다 까다로웠던 문제였다
‘구현’에 초점을 둔 문제였으나
주어진 테스트케이스가 적어 디버깅이 조금 힘들었다

그래도, 몇가지 문제를 곱씹으며 느낀점은

1. 3,6,9 와 같이 ‘주어진’ 수가 위치하는 3의 배수의 ‘단계’가 있다고 생각
   
2. 해당 단계에서 ‘*‘와 ‘+’의 개수는 3의 배수의 ‘단계’로 표현할 수 있다
   정확히 각 단계를 step이라 하면,
   *의 개수 : step,
   +의 개수 : step * 2
   
3. 시작은 반드시 * 이며, 끝나는 것은 반드시 – 이다
   

이러한 부분에 집중하여 문제를 풀 수 있었다
처음에는 1부터 탐색하는 방식을 사용하였으나
INT_MAX 값에서 시간초과가 나서
반대로 ‘내려가는’ 방식으로 풀어 해결하였다

Code

#include<math.h>
#include<limits.h>

using namespace std;

typedef long long ll;

ll getMinValue(int step)
{
	return pow(3, step) + step * 2;
}

void dfs(int nowValue, int& answer, int mV, int pV)
{
	// 현재 값이 너무 적거나, 곱하기 수가 하나도 안남아 있다
	if (nowValue < 3 || mV == 0)
		return;

	// 더하기가 너무 많은 상황이다
	if (pV > mV * 2)
		return;

	if (pV == 0 && mV > 0)
	{
		while (mV > 1)
		{
			// 곱하기만 남았는데 3의 배수가 아닌 상황이므로 return
			if (nowValue % 3 != 0)
				return;

			nowValue /= 3;

			mV--;
		}
	}

	// 시작이 반드시 *이므로
	if (nowValue == 3 && mV == 1 && pV == 0)
	{
		answer++;
		return;
	}

	if (nowValue % 3 == 0)
		dfs(nowValue / 3, answer, mV - 1, pV);

	dfs(nowValue - 1, answer, mV, pV - 1);
}

int solution(int n) {
	int step = 1;
	int answer = 0;

	// 몇 번째 3의 배수에 위치하였는지를 체크하기
	{
		while (n >= getMinValue(step))
		{
			step++;
		}

		// 해당 step의 위치의 다음 단계이므로
		// 1빼준다
		step--;
	}

	// 어차피 마지막은 반드시 ++ 로 끝나기에
	// 미리 n과 plus의 수를 조절해준다
	dfs(n - 2, answer, step, step * 2 - 2);

	return answer;
}