[ 프로그래머스 ] Level 4 4단 고음 ( Java )

2017 카카오코드 예선

문제 설명

문제 설명

4단 고음

I'm in my dream~↗ ~↗ ~↗

IU는 본인의 장기인 3단 고음으로 유명하다. 그러던 그녀가 어느 날 4단 고음을 성공했고 그녀의 고음은 학계에서 연구가 될 만큼 유명해졌다 [1].

[1] 견두헌, 배명진. “아이유의 고음 발성 특성 분석”, 한국음향학회, 2011년 춘계학술대회 학술발표논문지

폭포 밑 득음 수련을 하던 어느 날, 그녀는 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으로 주어진다.

출력 형식

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

예제 입출력

nanswer

15	1
24	0
41	2
2147483647	1735

예제에 대한 설명

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

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

처음에 문제를 보고 방법을 두가지를 생각했다.

처음에는 프로그래머스는 시간 초과도 중요한 고려사항이라 static변수를 선언하여 값을 미리 2^31-1 인 Integer.MAX_VALUE를 모두 계산해보려고 하였다.. int[]로는 안되서.. ArrayList에 넣으려고도 하였는데, 사이즈가 너무 커서 그냥 다 안되더라.. 시도 조차 못해봤다!

그래서 다른 방법이 계산을 해야겠다 였다.

[이전값]*++ / *+[이전값]+ / *[이전값]++ 이런 경우의 수가 있다는 것을 확인하고, 이전 값이 되려면 2를 뺴고, 3으로 나누어 떨어져야 계산이 가능했다.

그래서 수식을 짜보려고 했는데... 진짜 안되더라..... 나는 바보라서 k가 *와 (++)의 개수 조건이라면

n = 3^k 고 k/2 이거를 계산을 못하는 바보가 나였다.. k가 같아야 한다..

조건을 주려면 2* log(현재값)/log(3) = (+개수) 이 동일하면 계산이 되고, 이것보다 +의 개수가 크면 불가능 한 거였다.

이걸 그렇게 머리가 안돌아가서 검색해서 찾아봤다....

이 수식만 알면 나머지는 쉽게 계산이 된다..

Java 코드

class Solution {
        public int solution(int n) {
            int answer = 0;
            return check(n-2,2);
        }

        private int check(int n, int p) { // n이 현재 값 , p가 plus의 개수
            if(n==3 && p==2)return 1;
            else if( n<3 ||  Math.log(n)/Math.log(3) *2 < p)return 0;
            else if(n==3 && p==3) return 0;

            return check(n-1,p+1)+(n%3==0&&p>1?check(n/3,p-2):0);
        }
    }

마지막으로 계산을 할 떄 , 남은 n이 3이고, +의 개수가 2개가 남으면 계산은 완전한 수식이 된다. 그래서 +1을 해줄 수 있도록 1을 리턴한다.

그리고 만약 n이 3으로 나누어 떨어지면 한번 더 계산을 하면서 돌고, 아니면 1씩 빼주면서 +의 개수를 뺴면서 계산하면 된다.

쓰고 나니 코드가 진짜 너무 짧더라.. 이렇게 간단한거 수식이 머리로 안들어와서 이걸 못했다니

앞으로 저런 수식을 사용하는 일에 익숙해 져야지 되겠다ㅠㅠㅠ

프로그래머스 결과

결과는 이렇게 나온다..

테스트 케이스는 하나 뿐이었던 걸로....