Skip to main content

[level 4] 4단 고음 - 1831

Intro

문제 링크

문제 설명​

IU는 본인의 장기인 3단 고음을 넘어 4단 고음, 그리고 그 이상의 고음을 연구하고 있습니다. 고음 규칙은 * 와 + 기호를 사용하여 기록하며, 규칙은 다음과 같습니다.

  • 3단 고음은 1단계에서 음높이가 3배가 되며(_), 2단계와 3단계에서 음높이가 각각 1씩 증가합니다(+). 즉, 3단 고음 한 번은 _++ 로 표현됩니다.
  • 규칙 1: 특정 단어를 선택하여 글자 사이마다 같은 기호를 넣을 수 있습니다.
  • 규칙 2: 한 번 쓰인 소문자(특수기호)는 다시 쓰일 수 없습니다.

시작 음높이는 항상 1이며, * 기호는 현재 음높이에 3을 곱하고, + 기호는 1을 더합니다. 최종 음높이 이 주어졌을 때, 이를 만들 수 있는 서로 다른 '올바른 문자열'의 개수를 구해야 합니다. 올바른 문자열은 항상 *로 시작하며 마지막은 ++로 끝나야 합니다. 또한, 문자열을 뒤에서부터 탐색할 때 항상 +의 개수가 *의 개수의 2배 이상이어야 한다는 제약이 있습니다.

입력 형식​

  • 입력은 5 이상 이하의 정수 으로 주어집니다.

출력 형식​

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

입출력 예시​

nanswer
151
242
412
21474836471735

예제에 대한 설명​

예시 3()의 두 가지 경우:

  1. *++++++
  2. *+**+++++

구현 코드​

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);
        }
    }

성능 요약​

메모리: 82.8 MB, 시간: 730.41 ms

채점결과​

정확성: 100.0

합계: 100.0 / 100.0