4단고음 - Level4 , DFS

programmers.co.kr/learn/courses/30/lessons/1831

코딩테스트 연습 - 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으로 주어진다.

출력 형식

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

예제 입출력

n	answer
15	1
24	0
41	2
2147483647	1735

예제에 대한 설명

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

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

 

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.

#include<math.h>

int answer;

void dfs(int value, int cnt){
    
    if(value<3 ||  ((int)(log(value) / log(3)) << 1)<cnt)return; //log(value)/log(3) 은 *의 개수를 의미한다. 
    if(value==3){ //* 한개만 남겨졌을 때
        if(cnt ==2) answer++;
        return;
    }

    //이 부분에서 먼저 3으로 나눌수 있는지 없는지로 가지치기를 해야한다. 
    
    if(value%3 ==0 && cnt>=2){ //애초에 조건이 만족되지 않으면 더이상 탐색을 하지 않는다 -> 백트래킹, 가지치기 , 여기서 가지치기를 dfs재귀 후 기저조건에서 하지않고 dfs재귀 전에 해야한다 전에해야지 3으로 나눌 수 있는 숫자인지 아닌지 판별 가능하기 때문이다.
        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;
}