[2017 카카오코드] 4단 고음 for JAVA

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

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

[문제 설명]

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단 고음 문자열이 몇 가지나 있는지 궁금하다. 여러분의 도움이 필요하다.

[풀이]

답을 주고 연산의 경우의 수를 묻는 문제는 대부분, 이진 검색이거나 역방향 연산이 많은 것 같다.

조건을 잘 생각해보면, *++이 하나의 세트다. *뒤에는 꼭 +이 2개가 와야 한다. 

그리고 문자열 앞에 +이 올 수 없고, 문자열 맨 뒤에 *이 올 수 없다.

문자열 맨 뒤는 적어도 ++이 와야한다.

 

하나의 예를 통해 알아보면

15의 경우의 수를 구한다.라고 하면 결국 마지막은 "(*와+의 조합)++"이 올 것이다.

그럼 "(*와+의 조합)++" = 15이면 +는 곧 1이니 "(*와+의 조합)" = 13이라는 방식이 나온다.

 

15 = 15

14+ = 15

13++ = 15

12+++ = 15 

(*은 x3이므로 어떤 수를 3곱해서 12가 나온 지 판단한다면 4* 가 나온다. 12=4*)

[4*+++, 11++++]

[3+*+++, 10+++++]

(3이 나오면 종료, 하지만 ++를 잘 봐야 한다. *하나당 ++를 마킹해야 한다. 현재 남아있는 +은 2개이므로 올바른 조건.)

[9++++++]

(++당 * 하나가 온다. +가 6이므로 ***(27)이 앞에 와야 하지만, 9가 27이 될 수는 없으므로 올바르지 못한 조건.)

 

답 : 1 -> *+*+++

 

[코드]

public int solution(int n) {
        int answer = 0;
        answer = getCases(n, 0);
        return answer;
    }
    
    public int getCases(int n, int plus) {
        int result = 0;
        
        if(n == 3 && plus == 2) {                //n = 3이고 나머지 +가 2개면 *++세트로 올바른 조건으로 마무리된다.
            return 1;
        }else if(n==2) {                        //n = 2로 떨어지면 올바르지 못한 조건.
            return 0;
        }else if(n==3){                            
            return 0;
        }
        
        if(Math.pow(3, plus/2) > n) {            // 잔여 +의 개수 /2 만큼 3을 제곱한 수가 남은 수 n보다 크면 올바르지 못한 조건.
            return 0;
        }
        
        if(n % 3 == 0) {                                    //n 이 3으로 나뉘고
            if(plus >= 2) {                                    //+가 2개 이상이라면
                result += getCases(n / 3, plus - 2);        //올바른 조건이므로 *++으로 만들어줌.
            }
            result += getCases(n - 1, plus + 1);            //n을 빼주고 +를 붙힌다.
        }else {
            result += getCases(n - 1, plus + 1);
        }
        
        return result;
    }

테스트 케이스 통과

느낀 점: 넘무 어렵다. 처음에는 문자열, 이진 탐색, 완전 탐색 등으로 문제 해결을 생각했다. 결국에는 다른 코드를 참조하여 나만의 방식으로 푸는 것으로 풀었지만, 모든 것을 주어진 방식 그대로 생각하면 안 된다는 생각을 할 수 있게 해 줘서 좋은 시간이었다.