프로그래머스: 4단 고음⭐⭐⭐⭐

난이도 ⭐⭐⭐⭐
유형 : DFS

🧐 문제

문제 설명

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

예제에 대한 설명

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

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

---

🔍힌트

DFS와 가지치기를 사용하는 문제이다.
반대로 계산해주며, 1이 되도록 만들어 주어야한다.

15는 [**++++ ~ *++*++] = 13 ~ 17 범위 내에 들어가고, 41은 [***++++++ ~ *++*++*++] = 33 ~ 53 범위 내에 들어간다.

각 음높이마다 3단 고음의 횟수는 정해져 있으며,
이는 *와 +의 등장 횟수 또한 정해져 있다는 것을 뜻한다.

이러한 특징을 이용하여 문제를 풀어야한다.

---

✏️ 나의 풀이

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int result;

void dfs(int n, int three, int plus) {
    // ++*나 +*+ 같은 경우
    if(three * 2 < plus || three < 0 || plus < 0 || n == 0) return;
    if(three == 0 && plus == 0 && n==1) {
        result++;
        return;
    }

    dfs(n-1, three, plus-1);

    if(n%3 != 0) return;
    dfs(n/3, three-1, plus);
}

int find_depth(int n) {
    return log(n)/log(3);
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n) {
    result = 0;
    int depth = find_depth(n);
    dfs(n, depth, depth*2);

    return result;
}

✔️ 다른 사람의 풀이

#include <math.h>
 
int cnt;
void calc(int cur, int plus) {
    if (cur < 3 || ((int)(log(cur) / log(3)) << 1) < plus) return;
    if (cur == 3) {
        if (plus == 2) cnt++;
        return;
    }
 
    if (cur % 3 == 0 && plus > 1)
        calc(cur / 3, plus - 2);
    calc(cur - 1, plus + 1);
 
}
 
int solution(int n) {
    cnt = 0;
    calc(n - 2, 2);
    return cnt;
}

🧐 분석

1. 마지막 2자리는 “++”일 수 밖에 없으므로, DFS에 들어가기전에 n-2를 해주고 있다.
2. 곱한 횟수와 더한 횟수를 따로 분리해주지 않고, plus만 유동적으로 변화시키며 사용하고 있다. “(int)(log(cur) / log(3)) « 1 < plus”를 통해 +, ++*를 거르고 있다.
3. (int)(log(cur) / log(3))를 사용하여 3단 고음의 횟수를 정하고 있다.

Programmers 카테고리 내 다른 글 보러가기