프로그래머스 - 4단 고음

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1831

프로그래머스

N을 만들 수 있는 경우의 수를 구하는 문제였다.

 

*++이 3단고음이고 *은 3을 곱하기, +는 1을 더하기이다. 3단고음 중간에 3단 고음을 실행할 수 있다.

 

문제 풀이

 

처음에 1에서 시작해 N을 만드는 방법으로 했는데, 시간 초과가 계속 났고 풀이를 참고해서 다시 풀었다..

N부터 시작해서 1까지 도달하게 했고, *는 3으로 나누기, +는 3으로 나눈 나머지를 빼도록 했다.

 

3으로 나눠진다면 *와 +++의 상황으로 나눴고, 나눠지지 않는다면 나머지만큼 +하는 경우로 생각했다. 이때 사전에 *의 최대 개수를 구해 +의 개수가 *의 개수 x2보다 커지는 경우 가지치기를 했다. 그렇게 나온 숫자가 1이면서 +와 *의 개수가 맞는다면 개수를 세줬다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

int N;
int cnt;
int maxMul;


/*
뒤에서부터 시작
num이 3으로 나눠 떨어지는 경우 -> *
num이 3으로 나눠 떨어지지 않을 때 -> +
*/

void dfs(int num, int plusCnt, int mulCnt){
    if(plusCnt > maxMul*2) return; //* 개수 초과
    
    if(num == 1 && plusCnt == mulCnt*2){ //숫자 완성
        cnt++;
        return;
    }
    
    if(num%3==0){        
        if(plusCnt >= (mulCnt+1)*2) //한 번 더 나눌 수 있다면 *
            dfs(num/3, plusCnt, mulCnt+1);
        dfs(num-3, plusCnt+3, mulCnt); //3번 + 하는 경우
    }
    else{ //+
        dfs(num-(num%3), plusCnt+(num%3), mulCnt);
    }
    return;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n) {
    int answer = 0;
    N = n;
    cnt = 0;
    
    maxMul = log(n)/log(3); //* 최대 개수
    dfs(n,0,0);
    answer = cnt;
    return answer;
}