프로그래머스 - 4단 고음

프로그래머스 - 4단 고음

카카오는 테스트 케이스가 1개로 퉁쳐져서 나올 때가 있어서 디버깅이 너무 불편한 경우가 많다.

이 문제는 일단 기본적으로 dfs + 가지치기 문제이다.

n이 주어졌을 때, 해당 숫자가 문제에서 주어진 조건에 만족할 때 n을 만들 수 있는 경우가 몇가지인지를 체크하면 되는 문제이다.

문제에선 *++... 등의 문자열을 주는데, 여기서 *는 곱하기 3연산이고, +는 더하기 1연산이다.
* 뒤에는 2개의 + 연산이 올 수 있는데, *가 **++++, *+*+++등의 형태로 연속적으로 주어질 수 있다.
시작은 1부터해서 *를 만날때마다 곱하기 3을 해주고, +를 만날때마다 더하기 1을 해주면 된다.

예를 들어, **++++의 경우엔 13을 의미한다.

41을 나타내는 경우는 **++++*++, *+**+++++ 로 두 가지 경우가 존재한다.

해결 방법은 다음과 같다.

1. 먼저 k개의 *를 통해 나타낼 수 있는 범위의 최솟값은 항상 k-1개의 *을 통해 나타낼 수 있는 범위의 최댓값보다 크고, k+1개의 *을 통해 나타낼 수 있는 범위의 최솟값보다 작다. 즉, n이 주어졌을 때, 몇 개의 k값을 가지는지 바로 알아낼 수 있다.

• 만약 k가 3일 때, ***++++++의 경우 최솟값이고, *++*++*++가 최댓값이다.

2. n을 나타내는 문자열의 맨 뒤 2개는 항상 ++이다.

위 조건을 이용해서 dfs를 돌텐데, n이 주어졌을 때, n-2부터 dfs를 수행하면서 +가 몇 번 발생했는지, *가 몇 번 발생했는지를 체크하면서 가지치기를 수행해준다.
dfs를 도는 개념은 n의 값에 따라서 역으로 연산을 추가해가는 방식이다.
즉, 곱하기 3은 나눗셈 3으로, 더하기 1은 빼기 1로 치환해준다.

예를 들어 13을 만들기 위해서는
13 -> 12 -> 11 -> 10 -> 9 -> 8 ... -> 1
13 -> 12 -> 4 -> 3 -> 2 -> 1
13 -> 12 -> 4 -> 3 -> 1
등의 순서로 연산을 진행할 수 있을 것이다.
이 때, 만약 *가 3번 발생하는 n이라면 +갯수는 항상 6이하여야하고, *갯수는 3이하여야 한다.
또한 +의 갯수가 *의 갯수의 2배를 넘겨서도 안되고, n은 항상 1보다 커야한다.

위 조건에 맞춰서 가지치기를 수행하면서 조건에 맞았을때만 정답을 1증가시켜주면된다.

코드는 아래와 같다.

#include <cstdio>

int answer;

void dfs(int high, int cur, int p, int m)
{
    if(cur < 3)
        return;
    if(m > high) 
        return;
    if(p > (high << 1))
        return;
    if((m << 1) > p)
        return;
    
    if(cur == 3 && ((m + 1) << 1) == p) {
        answer++;
        return;
    }
    
    if(cur % 3 == 0)
        dfs(high, cur / 3, p, m + 1);
    dfs(high, cur - 1, p + 1, m);
}
int solution(int n) {
    if(n % 2 == 0)
        return 0;
    
    int high_note[20] = { 1 };
    int tmp = -2;
    for(int i=1;i<20;i++) {
        high_note[i] = high_note[i - 1] * 3 - tmp;
        tmp += 4;
    }
    int high = 19;
    for(int i=1;i<20;i++) 
        if(n < high_note[i]) {
            high = i - 1;
            break;
        }

    answer = 0;
    dfs(high, n - 2, 2, 0);
    
    return answer;
}