[LV4] 4단 고음

1. 문제

1) 문제 링크

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

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

 

2) 설명

문제를 읽어보니 *++을 이용해서 n을 만들어내는 경우의 수를 구하는 문제다.(*의 의미는 곱하기 3, +는 더하기 1이다)

다만 여기에 규칙이 몇 개가 있다.

 

규칙 1 : *++은 반드시 *가 나온 후에 + 두 개가 나와야 한다.

규칙 2 : *++ 계산을 하는 중간에 새로운 *++이 시작할 수도 있다.

 

예를 들어

1. *++*++은 올바르다. 이대로 계산을 하면

*	+	+	*	+	+
3	4	5	15	16	17

이렇게 17을 만들 수 있다.

 

2. 반면 *+++*+ 은 올바르지 않다.

규칙 1에 위배된다.

 

3. *+*+++은 올바르다.

규칙 3에 따라 *+ ( *++) + 이렇게 중간에 새로운 *++이 시작한 것이다.

*	+	*	+	+	+
3	4	12	13	14	15

이렇게 15를 만들 수 있다.

 

 

2. 풀이

1) 알고리즘

    : 재귀

 

2) 풀이 설명

처음에는 재귀 반복으로 해결하려 했는데 시간초과가 났다ㅠㅠ 그래서 다른 풀이들을 약간 참고했다.

 

이 풀이는 반드시 * 뒤에 ++가 나와야 한다는 규칙을 이용한다.

모든 *가 +에 우선해야 한다는(ex : ******++++++...) 의미가 아니라 *++ 쌍을 이루는 3단 고음이 * + + 순서대로 나와야 한다는 것이다.

dfs(재귀함수)에는 만들고 싶은 수 n과 남아있는 +의 수 plusCnt를 인자로 받는다.

예를 들어 20을 만들고 싶고 +가 4개가 나온 상황이라면 dfs(20, 4)가 된다.

재귀적으로 dfs함수를 호출해 n = 3, plusCnt = 2까지 줄일 수 있는 경우의 수를 세는 게 문제를 푸는 방법이다.

n이 3, plusCnt가 2라는 말은 *++를 의미한다.

n = 3, plusCnt = 2까지 못 만들면 해당 {n, plusCnt} 상태에서는 규칙에 맞게 *++을 만들 수 없다.

 

또한 (앞으로 나올 수 있는 *의 최대 개수 < 반드시 나와야 할 *의 최소 개수) 라면 더이상 재귀함수를 진행하는 것이 무의미하다. 왜냐면 어떻게 진행을 해도 최소한 나와야 하는 *의 개수를 만들 수 없게 되기 때문이다. -> log(n)/log(3) < (plusCnt + 1)/2 이면 진행을 멈춘다. ( log(n)/log(3)은 (로그 3의 n), 즉 3을 몇 번 제곱해야 n이 되냐는 말이다) (plusCnt + 1)인 이유는 plusCnt가 홀수 개일 때를 대비하기 위함이다. (ex : plusCnt = 5일 때 *는 최소 3개가 나와야 한다. 그러려면 (5 + 1)/2로 해줘야 함)

 

n이 3으로 나누어 떨어진다면 + plusCnt가 2 이상이라면 dfs(n/3, plusCnt - 2)를 호출한다.

n을 3으로 나눈다는 것은 *가 하나 등장했다는 의미이고 plusCnt가 2개 이상 있어야 규칙 1을 위반하지 않을 수 있다.

 

n이 3으로 나누어 떨어지든 안 떨어지든 dfs(n - 1, plusCnt + 1)을 호출한다.

n에서 1을 뺀다는 것은 +를 하나 늘렸다는 말이므로 plusCnt + 1을 해주는 것이다.

 

이 과정을 n은 3, plusCnt는 2가 될 때까지 반복해주면 된다.

 

참고로 첫 호출은 dfs(n - 2, 2)로 해주면 된다. 왜냐하면 마지막 두 개는 반드시 ++이기(plusCnt = 2) 때문이다.(그냥 dfs(n, 0)해도 상관 없다)

 

예를 들어서 n = 13일 때 어떻게 진행되는지 보자.

dfs(11, 2) 호출

-> 11%3 != 0이므로 dfs(10, 3)만 호출

    -> 10%3 != 0이므로 dfs(9, 4)만 호출

        -> 9%3 == 0이고 4(plusCnt) >= 2이므로 dfs(3, 2) 호출

            -> n == 3, plusCnt == 2 이니까 return 1

        -> dfs(8, 5) 호출

            -> log(8)/log(3)은 2보다 작고 (5(plusCnt) + 1)/2)인 3보다 작으므로 return 0

        : 1 + 0 해서 return 1

    : return 1

: reuturn 1

 

이런 식으로 진행된다.

 

3. 코드

#include <math.h>

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
using namespace std;

int dfs(int n, int plusCnt){
    if(n < 1 || log(n)/log(3) < (plusCnt + 1)/2){
        // log(n)/log(3)	: 앞으로 나올 수 있는 최대한의 * 횟수(n이 되기 위해 3을 거듭제곱해야 하는 횟수)
        // (plusCnt + 1)/2	: *가 나와야 하는 최소한의 횟수
  		// 앞으로 *가 최대로 나오는 경우(log(n)/log(3)) 가 반드시 나와야 하는 *의 횟수((plusCnt + 1)/2) 보다 작다면 더 재귀를 진행해봤자 무의미함으로 return
        return 0;
    }
    if(n == 3 && plusCnt == 2){
        // * : 하나, + : 둘 이므로 1 return
        return 1;
    }
    
    int ret = 0;
    if(n%3 == 0 && plusCnt >= 2){
    	//3으로 나눠지고 남은 +가 두 개 이상이어야 *가 나올 수 있음
        ret += dfs(n/3, plusCnt - 2);
	}
    ret += dfs(n - 1, plusCnt + 1); //+ 하나를 늘리는 경우
    
    return ret;
}

int solution(int n) {
    return dfs(n - 2, 2); // 시작 시 맨 마지막 두 개는 무조건 ++이어야 하므로 plusCnt를 2로 시작
}

 

 

4. 느낀점

오랜만에 log를 봤다...

종종 사용하면 좋을 것 같다.