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

[문제]

4단 고음

 

I'm in my dream~↗ ~↗ ~↗

IU는 본인의 장기인 3단 고음으로 유명하다. 그러던 그녀가 어느 날 4단 고음을 성공했고 그녀의 고음은 학계에서 연구가 될 만큼 유명해졌다 [1].

[1] 견두헌, 배명진. “아이유의 고음 발성 특성 분석”, 한국음향학회, 2011년 춘계학술대회 학술발표논문지

폭포 밑 득음 수련을 하던 어느 날, 그녀는 4단 고음이 끝이 아님을 깨달았다. 3단 고음 직후 3단 고음을 연이어하거나, 3단 고음 중 다시 3단 고음을 해서 음높이를 올리는 방법이다. 어떤 순서로 3단 고음을 했는지에 따라 최종 음높이가 달라지기 때문에, 연속 3단 고음을 연습할 때마다 그 결과를 기록으로 남기기로 했다.

3단 고음은 다음과 같이 적용된다. 1단계에서는 음높이가 세 배가 되며, 2단계와 3단계에서 음높이가 각각 1씩 증가한다. 이를 기록으로 남길 때 * 와 + 기호를 사용하기로 했다. 즉, 3단 고음을 한 번 한 경우는 문자열로 나타내면 다음과 같다.

*++

이때 3단 고음을 마치고 연달아 3단 고음을 한 경우는 *++*++ 와 같이 표현할 수 있다. 3단 고음의 2단계를 마친 후 3단 고음을 새로 시작한 다음, 나머지 단계를 이어서 하는 경우는 *+*+++로 표현할 수 있다. (강조된 부분이 2번째 3단 고음을 부른 부분이다.)

이와 같이 * 와 + 로 구성된 문자열이 3단 고음의 규칙을 적용하여 만들 수 있는 문자열인 경우 '올바른 문자열'이라고 하자. 다음의 문자열은 3단 고음의 규칙으로 만들 수 있는 문자열이 아니므로 올바른 문자열이 아니다.

• +**+++
• *+++*+

올바른 문자열에 대해 음높이는 다음과 같이 계산할 수 있다. 시작 음높이는 항상 1이며, 문자열의 처음부터 순서대로 * 기호의 경우 3을 곱하고 + 기호의 경우 1을 더한다. *+*+++ 의 음높이를 계산하는 과정을 예로 들면 아래와 같다.

시작 음 높이: 1

*+*+++

*3

+1

*3

+1

+1

+1

최종 음높이: 15

그날 기분에 따라 최종 음높이를 정하는 IU는 최종 음높이를 결정했을 때 서로 다른 3단 고음 문자열이 몇 가지나 있는지 궁금하다. 여러분의 도움이 필요하다.

입력 형식

• 입력은 5 이상 2^31-1 이하의 정수 n으로 주어진다.

출력 형식

• 입력을 만족하는 서로 다른 문자열의 수를 리턴한다.

예제 입출력

nanswer

15	1
24	0
41	2
2147483647	1735

예제에 대한 설명

세 번째 예제의 두 가지 경우는 다음과 같다.

**++++*++
*+**+++++

 

 

[풀이]

 

1) 처음에는 1부터 n까지 커지게 하면서 *와 +의 개수를 늘려주면서 값을 구해가려고 했는데 그것보다는 3이 남을 때까지 n에서 빼주어도 된다. 

 

2) 문자열의 마지막은 무조건 ++이기 때문에 * + + 일때 중간에 다른 3단 고음이 와도 ++ 로 끝날 수 밖에 없다. 

dfs(n-2, 2) 로 시작해도 된다. 

 

n-2는 + 는 1씩 더해주는 것이기 때문에 n-2로 만들고 2는 +의 개수이다. 

 

3) 이 문제는 가지치기를 잘 해야한다.(하지 않으면 마지막 테스트 케이스에서 시간 초과가 난다. )

• 첫 번째 가지치기는 value가 1보다 작을 때 (제대로 된 문자열이 아닌 경우)
• 그리고 *의 개수를 계산한다. 여기서 조금 버벅댔는데 value에 로그를 취한 후 log3으로 나눠주면 *의 개수이다.
• value == 3이 됐을 때 (맨 앞의 *만 해주면 될 때 ) cnt == 2인 경우에만 정답의 개수를 늘려준다. 

그리고 dfs를 재귀호출하는데 value가 3으로 나눠지고 +의 개수가 2보다 클 때는 * 을 해준다. 

dfs(value /3 , cnt-2)

 

그렇지 않으면 

dfs(value -1, cnt+1) : +의 개수만 늘려준다. 

 

---

 
#include <cmath>
 
using namespace std;
 
int answer = 0;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
void dfs(int value, int cnt) 
{
    //log(value) / log(3) 는 *의 개수를 계산한 것.
    if (value < 1 || 2*log(value) / log(3) < cnt) return;
    if (value == 3) { //*만 남겨졌을 때 
        if (cnt == 2) answer++; //+는 2개여야 한다. (*++)
        return;
    }
    
    if (value % 3 == 0 && cnt>= 2) {
        dfs(value/3, cnt-2);
    }
    dfs(value-1, cnt+1);
}
int solution(int n) {
    answer = 0;
    
    dfs(n-2, 2); //2는 현재 +의 개수 / n-2는 최대 음 높이 
    return answer;
}