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

문제코드) https://programmers.co.kr/learn/courses/30/lessons/1831

풀이)

앞에서부터 규칙을 적용해서 최종 음높이가 나오는 경우를 세면 시간초과가 걸린다.

프로그래머스의 다른 문제, 점프와 순간이동 처럼 뒤에서부터 경우를 생각해서 풀어야하는 문제다.

2가지 조건을 생각하면 된다.

1. 처음 문자열 시작은 무조건 *이다. 즉 값은 3부터 시작한다.

2. 마지막 문자열 2글자는 무조건 ++이다. 

이 조건들을 생각하면서, n-2의 값을 확인하면 된다.

(++) = 2 를 제외한 값

주의점

시간제약이 꽤 까다롭기 때문에,  

현재 +개수에 맞춰서 표현할 수 있는 값이 최종 나와야하는 값보다 크다면 더이상 확인해보지 않게 넘어가도록 표현해줬다.

코드)

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
#include<cmath>
int result;
void dfs(int n,int cnt){ // n은 지금까지 표현된 값, cnt는 +의 개수
    if(n<3 || pow(3,cnt/2) > n) return;
    if(n==3){
        if(cnt == 2) result++; // 첫시작이 *이고 +개수가 2개로 규칙을 만족한다면
        return;
    }
    //덧셈이 2개 이상이고, 3으로 나누어떨어질수 있으면 *사용 가능
    if(n%3 == 0 && cnt >= 2) dfs(n/3, cnt - 2);

    dfs(n-1, cnt + 1);
}

int solution(int n) {
    result = 0;
    dfs(n-2,2); //맨 뒤에는 무조건 ++이기때문에 n-2값부터 확인하면 된다.
    return result;
}