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

문제 주소 : programmers.co.kr/learn/courses/30/lessons/1831

코딩테스트 연습 - 4단 고음

문제 확인

 

간단하게 시뮬레이션처럼 풀 수 있지만 시간 초과가 납니다. 또한 단순 dfs로 풀어도 시간 초과가 나게 됩니다. 따라서 가지치기, 혹은 추가 조건을 통해서 통과할 수 있습니다.

* 이후에 2개의 + 가 나와야 하므로 이를 이용하여 조건을 만들 수 있습니다.

하향식 dfs와 가지치기를 통해 풀 수 있습니다.

 

풀이

 

하양식 dfs를 통해 탐색횟수를 줄일 수 있습니다. 초기값부터 시작하여 n으로 가는 경우 불필요한 탐색이 많이 일어나므로 n에서 시작하여 값을 줄여나가 결과를 찾습니다.

현재 값을 cur로 두며 plus 값은 *와 쌍을 이루면 -2, 쌍을 이루지 않고 추가하면 +1로 하여 문제의 조건을 맞춥니다.

문자열에서 마지막 2 문자는 "++"일 수밖에 없으므로 초기 n 값을 -2, +개수를 2로 설정하고 탐색을 시작합니다.

dfs 탐색의 가지 수는 *, +를 추가하는 경우로 2개로 볼 수 있습니다.

1. * 를 추가하는 경우 : 이 때는 현제 남은 변수가 3으로 나눌 수 있는 경우, +의 개수가 2개 이상 있는 경우만 추가하여 탐색 횟수를 줄입니다.
2. + 를 추가하는 경우는 별다른 조건 없이 탐색합니다.

종료 조건은 값이 3이며 남은 +의 개수가 2개일 때 올바른 문자열이 됩니다. 그 외 값이 3 미만이거나 남은 값에서 추가할 수 있는 *의 개수가 + 개수와 맞지 않다면 미리 종료합니다. 이를 통하여 가지치기를 진행합니다.

 

코드

#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;
}