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

문제

문제 설명

 

풀이

 

[풀이]

 

처음에 1부터 시작해 최종 음높이 n이 되는지 탐색하도록 코드를 짰는데, 경우의 수가 너무 많아 시간 초과가 걸렸다.

그래서 역으로 n부터 시작해 역으로 1까지 돌아오도록 코드를 짰다.

이 경우 코드의 패턴은 n을 3으로 나눌 수 있는 경우와 없는 경우로 나뉘는데

​

1. n을 3으로 나눌 수 있는 경우 n/3 의 경우를 재귀로 탐색하면서 *의 개수를 1 늘려준다.
2. n에서 1을 뺀 다음 +의 개수를 1 늘려준다.

​

위와 같이 탐색해 나가면 된다.

​

[주의]

1. +의 개수가 늘어난 만큼 *의 개수가 늘어나는데 [사용한 +의 개수/2 - 사용한 *의 개수] 가 앞으로 추가되어야 할 *의 개수다. 그러므로 추가해야할 *의 개수 n을 3^n으로 구하고, 현재 수보다 큰지 판단해 만약 크다면 가지치기로 제거해 속도를 빠르게 했다.
2. 무조건 패턴 중 처음은 *로 시작하고 마지막은 ++이 두개가 포함되어야 하므로, n-2부터 시작해 3으로 끝나는 경우를 찾는다.
3. 패턴이 항상 *가 먼저 나오므로, +의 개수가 *의 개수의 2배보다 많아지는 경우는 불가능 하다.

​

그리고 이 문제를 풀 때 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해야한다.

왠지 모르겠는데 solution에서 초기화 하지 않으면 정답 처리가 되지 않는다...

 

 

Code

 

 

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
#include<cmath>
using namespace std;

int answer =0;
void calc(int nowNum, int plusCnt, int multiCnt)
{
    if (plusCnt<(multiCnt-1)*2)
    {
        return;
    }
    int n;
    while(nowNum>=3)
    {
        if (nowNum==3){
            if (plusCnt%2==0)
            {
                if((plusCnt/2)==multiCnt)
                {
                    answer+=1;
                }
            }
            return;
        }
        n = plusCnt/2-multiCnt;
        if (pow(3,n)>nowNum)
        {
            return;
        }
        if  (nowNum%3==0)
        {
            calc(nowNum/3, plusCnt, multiCnt+1);
        }
        nowNum-=1;
        plusCnt+=1;
    }
}

int solution(int n) {
    answer=0;
    calc(n-2, 2,1);
    return answer;
}

 

---

 

예외 처리를 제대로 안해서 약간 오래 걸렸다;;

 

프로그래머스