문제

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

3단 고음 직후 3단 고음을 연이어하거나, 3단 고음 중 다시 3단 고음을 해서 음높이를 올리는 방법이다. 어떤 순서로 3단 고음을 했는지에 따라 최종 음높이가 달라지기 때문에, 연속 3단 고음을 연습할 때마다 그 결과를 기록으로 남기기로 했다.

3단 고음은 다음과 같이 적용된다. 1단계에서는 음높이가 세 배가 되며, 2단계와 3단계에서 음높이가 각각 1씩 증가한다. 이를 기록으로 남길 때 * 와 + 기호를 사용하기로 했다.

기분에 따라 최종 음높이를 정하는 IU는 최종 음높이를 결정했을 때 서로 다른 3단 고음 문자열이 몇 가지나 있는지 궁금하다.

---

입력

5 이상 2^31-1 이하의 정수 n

---

출력

서로 다른 문자열의 수를 리턴

---

풀이

제한조건

• 5 이상 2^31-1 이하의 정수 n

접근방법

문제를 먼저 이해 해보자.
3단 고음 중 또는 3단 고음이 끝난 후 다시 3단 고음을 통해 최종 음높이를 올릴 수 있다.

3단 고음은 *++의 형태롤 표현되므로, 만약 3단 고음을 여러번 하여 나올 수 있는 경우는 아래와 같다.

2번
*(*++)++
*+(*++)+
*++(*++)

3번
37    **++*++++
33    ***++++++
35    **+*+++++
37    **++*++++
39    **+++*+++
41    **++++*++
        
39    **+++*+++
45    *+*++*+++
41    *+**+++++
43    *+*+*++++
45    *+*++*+++
47    *+*+++*++
            
41    **++++*++
47    *+*+++*++
53    *++*++*++
49    *++**++++
51    *++*+*+++
53    *++*++*++

3단 고음을 2번 한 경우만 보았지만 뭔가 재귀적으로 진행될 것 같은 느낌이 든다. 또한 같은 수임에도 여러가지 경우가 나올 수 있음을 염두하자 ( 41의 경우 )

정리를 조금 하자면
이전결과를 Prev라고 두면 아래와 같이 3가지 경우로 계속 확장되어 나간다.

*(prev)++
*+(prev)+
*++(prev)

따라서 N에서 부터 역방향으로 돌아가서 만들어 질 수 있는것인지 카운팅 하는 방법을 사용하려 한다.

그렇다면, 문제에서 N에 주어졌을때, 과연 몇 번의 3단 고음이 필요할까?
k번의 3단고음을 사용해서 항상 최대 음 높이로 만든다고 생각해보자.
3단 고음이 종료되고 이어서 시작하는 것이 항상 큰 값으로 만들 수 있는 방법이다.
그렇다면 수식을 조금 생각해보자.

x = 1이라 두고.
k = 3단 고음의 수
f(k)를 구해보자!
f(1) = (3*x)+2 = 3x+2
f(2) = f(1)*3+2 = 9x+8
f(3) = f(2)*3+2 = 27x+26
...
f(k) = f(k-1)*3+2 = 3^k*x + 3^k-1

상수항을 무시하고 생각해보면, log(n)/log(3) 번의 3단 고음이 필요하다.

그럼 이제 문제를 해결하기 위해 생각해보자.
재귀적으로 함수를 수행하기 위한 원형을 아래와 같이 구성했다.

public int getSimulation(현재 수, 남은 곱하기의 수, 남은 더하기의 수){
        // 각종 종료 조건들
        
        // 다음 재귀로 나아가기 위한 조건들
        
        // 리턴
    }

*(prev)++
*+(prev)+
*++(prev)

수식은 항상 위와 같은 형식을 가진다.
마지막 2개는 항상 ++로 끝나게 되므로, 재귀적으로 수행할 함수의 시작은 func(n-2, numMul, numPlus-2)로 시작한다.

다음은 종료조건을 정의해보자.
3단 고음을 1번 할때, 3->4->5순으로 값이 만들어진다.
즉 아래 조건을 만족할때 정상적으로 만들 수 있는 조합인 것이다.

수	남은 곱셈	남은 덧셈
3	1	2
4	1	1
5	1	0

그리고 하나 더 고려해야 할 조건은 3단 고음이 하나의 곱셈과 2개의 덧셈으로 이루어 지므로, (numMul*2 < numPlus)가 참이 된다면, 만들 수 없는 수이다.
(3단 고음은 곱셈으로 시작해서 덧셈 2번이 발생한다. 덧셈 작업이 더 나중에 발생하므로, 곱셈이 먼저 줄어드는 경우는 잘못된 경우)

이번엔 다음 재귀로 가는 경우를 생각해보자.
뒤에서 부터 남은 덧셈의 갯수만큼 숫자를 빼면서, 3으로 나누어 진다면, 해당 수에서 다시 작업을 수행한다.

  for(int i = 0; i <= numPlus; ++i){
            if((n-i > 0) && (n-i) % 3 == 0){
                count += getSimulation((n - i) /3, numMul - 1, numPlus - i);
            }
        }

예시로 따라가보기

예시로 따라가보자
N=41이라 가정하자.
총 3번의 3단 고음으로 이루어지는것을 우리는 알 수 있다.
그리고 항상 ++로 끝나게 되므로
getSimulation(41-2, 3, 6-2)로 함수를 시작한다.

함수 내부에서 39~35의 숫자중 3으로 나누어 지는 수는
39와 36 2개가 만들어진다.
따라서 getSimulation(39/3, 3-1, 4-0) 과
getSimulation(36/3, 3-1, 4-3)가 호출.

getSimulation(39/3, 3-1, 4-0)은 다시
getSimulation(9, 2, 0)을 호출하며 (3,1,0)으로 1을 반환

getSimulation(36/3, 3-1, 4-3)은
getSimulation(4, 1, 1)을 호출하며 (4,1,1)으로 1을 반환

따라서 총 2개의 경우가 발생한다.

41    *+**+++++ 3->4->12->36->41
41    **++++*++ 3->9->13->39->41

이제 모든 항목을 코드로 작성하자.

---

코드

class Solution {
	// 몇 번의 곱셈이 필요한지 계산.
    public int getRemainMul(int n){
        return (int)(Math.log(n) / Math.log(3));
    }
    
    // 재귀적으로 수행하며 계산
    public int getSimulation(int n , int numMul, int numPlus){
    	// 종료 조건 정의
        if(numMul*2 < numPlus)
            return 0;
        if(n == 3 && numMul == 1 && numPlus == 0)
            return 1;
        if(n == 4 && numMul == 1 && numPlus == 1)
            return 1;
        if(n == 5 && numMul == 1 && numPlus == 2)
            return 1;
        
        // 재귀 수행 정의
        int count = 0;
        for(int i = 0; i <= numPlus; ++i){
            if((n-i > 0) && (n-i) % 3 == 0){
                count += getSimulation((n - i) /3, numMul - 1, numPlus - i);
            }
        }
        
        return count;
    }
    
    public int solution(int n) {
        int numMul = getRemainMul(n);
        int numPlus = numMul * 2;
        
        int result = getSimulation(n - 2, numMul, numPlus - 2);
        return result;
    }
}