[Lv3] 4단 고음

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

폭포 밑 득음 수련을 하던 어느 날, 그녀는 4단 고음이 끝이 아님을 깨달았다. 3단 고음 직후 3단 고음을 연이어하거나, 3단 고음 중 다시 3단 고음을 해서 음높이를 올리는 방법이다. 어떤 순서로 3단 고음을 했는지에 따라 최종 음높이가 달라지기 때문에, 연속 3단 고음을 연습할 때마다 그 결과를 기록으로 남기기로 했다.

3단 고음은 다음과 같이 적용된다. 1단계에서는 음높이가 세 배가 되며, 2단계와 3단계에서 음높이가 각각 1씩 증가한다. 이를 기록으로 남길 때 * 와 + 기호를 사용하기로 했다. 즉, 3단 고음을 한 번 한 경우는 문자열로 나타내면 다음과 같다.

*++

이때 3단 고음을 마치고 연달아 3단 고음을 한 경우는 *++*++ 와 같이 표현할 수 있다. 3단 고음의 2단계를 마친 후 3단 고음을 새로 시작한 다음, 나머지 단계를 이어서 하는 경우는 *+*+++로 표현할 수 있다. (강조된 부분이 2번째 3단 고음을 부른 부분이다.)

이와 같이 * 와 + 로 구성된 문자열이 3단 고음의 규칙을 적용하여 만들 수 있는 문자열인 경우 '올바른 문자열'이라고 하자. 다음의 문자열은 3단 고음의 규칙으로 만들 수 있는 문자열이 아니므로 올바른 문자열이 아니다.

• +**+++
• *+++*+

올바른 문자열에 대해 음높이는 다음과 같이 계산할 수 있다. 시작 음높이는 항상 1이며, 문자열의 처음부터 순서대로 * 기호의 경우 3을 곱하고 + 기호의 경우 1을 더한다. *+*+++ 의 음높이를 계산하는 과정을 예로 들면 아래와 같다.

시작 음 높이: 1

*	+	*	+	+	+
*3	+1	*3	+1	+1	+1

최종 음높이: 15

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

입력 형식

• 입력은 5 이상 2^31-1 이하의 정수 n으로 주어진다.

출력 형식

• 입력을 만족하는 서로 다른 문자열의 수를 리턴한다.

예제 입출력

n	answer
15	1
24	0
41	2
2147483647	1735

예제에 대한 설명

세 번째 예제의 두 가지 경우는 다음과 같다.

**++++*++
*+**+++++

 

 

---

 

*는 현재음에서 *3, +는 현재음에서 +1.

*가 한번 발생하면, 다음 언젠가에는 +가 2번 와야한다.

 

반대로 +가 있었다면 그 전에는 +가 1번, *가 1번은 있어야한다.(*가 +와 + 앞에)

 

이 조건을 만족하는 조합을 세면 된다.

 

이 문제, 왠지 전에 풀었던 점프와 순간이동과 비슷하지 않은가?

[Coding Quiz/programmers] - [Lv2] 점프와 순간이동

 

점프는 현재칸에서 +1 배터리 소모 +1,

순간이동은 현재칸에서 *2 배터리 소모 없음.

 

조금 다르다면 점프와 순간이동 때에는 *++의 순서적 관계가 없었다.

 

더 간단했던 점프와 순간이동도 그러했는데,

조건이 더 추가된 이 문제에서 앞에서 차근차근 모든 경우에 대해 곱해보고 더해보면서 답을 찾아갈텐가..(시간초과/메모리초과)

 

이번에도 역으로 생각해보자.

거꾸로 n에서부터 시작해서 시작음인 1로 도달하는 경우를 센다.

int answer;

public void cal(int add, int n) {
    if(Math.pow(3, add/2)>n) return;
    if(n==3) {
        if(add==2) {
            answer++;
        }
    } else if(n>3) {
        if(add>=2 && n%3==0) cal(add-2, n/3);
        cal(add+1, n-1);
    }
}

public int solution(int n) {
    answer = 0;
    cal(0,n);
    return answer;
}

 

위에서 말했듯이, 역으로 생각했을 때는 +로 끝나야 하고, ++가 왔을 때에는 *가 한번은 있었어야 한다.

 

n을 -1하면서 add를 1추가해주고,

add가 2이상이면서 n이 3으로 나누어 떨어질 때에는 거쳐온 add 표식을 2 빼주면서 3으로 나눠준다.

 

맨 처음에는 *로 시작했어야 하므로,

n이 3이면서, add가 2인 상태면

add 2를 소모하고 3으로 나눠주면서 1로 돌아올 수 있다.

 

 

이 조건으로도 충분할 것 같지만, 이대로는 시간초과가 발생한다.

아무 조건 없이 add를 늘리면서 -1했던.. 언젠가 *가 나오겠지 하면서 마냥 -1하던 것 때문에,

이렇게 3까지 도달해서 add가 2가 아니네 하면서 끝나기 전까지 무수히 많은 실행(-1씩.. 언제 3까지 가나..)과 그로 인한 시간이 걸린다.

 

역으로 가는걸 생각했을 때,

add가 0이면 *는 생각X

1이면 *는 아직 등장 전

2이면 *가 이제 1번 등장 가능(n>=2)

3이면 1,

4이면 2,

5이면 2,

6이면 3, ...

 

즉, add/2만큼 등장 가능.

 

n은 1부터 시작해서 3^(add/2)에 +가 1개 더 있거나 없거나이다. 심지어 +들이 앞에 위치해서 *3을 더 큰 수에서 시작했을 수도 있다.

즉, 3^(add/2) 이상이라는 소린데,

n이 3^(add/2) 미만이면 아예 성립이 안된다는 소리다. 이 n은 조건을 지키면서 1에 도달할 수 없으니 바로바로 return한다.

 

이 조건을 추가해주면 시간 초과없이 빠르게 답을 구할 수 있다.