Programmers 1831: 4단 고음

문제 조건

• 1단계에서는 음높이가 세 배가 되며, 2단계와 3단계에서 음높이가 각각 1씩 증가할 경우 3단고음 가능, 즉 *++ 형태만 가능하다.
  • 즉, 문자열은 항상 ++로 끝난다
• 3단 점프를 한 후에는 음계를 한 단계씩 두 번을 더 높게 내야한다. 하지만 굳이 연속으로 1단 점프를 할 필요는 없다.
  
  • 예) *+*+++

 

 

n= 41일 때 answer=2이다. 예시를 보자

41 = (~~~)++

39 = (~~~)

 

39를 만드는 방법은 아래와 같다.

38+

37++

36+++

12*+++, 35+++

11+*++, 34++++, (4**+++의 경우는 불가)

...

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

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

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