2017 Kakaotalk 예선 4단 고음
2017년도 카카오톡 코딩테스트 예선 문제인 4단 고음을 풀어보았다.
문제 링크 : 아이유 4단고음
1에서 시작해서 (*++) 를 적절히 조합해서 최종 숫자를 만드는 방법의 수를 구하는 문제이다. 1부터 시작해서 *와 +를 조합해가면서 최종 숫자를 만드려면 최종숫자보다 큰 수가 나올 때 까지 모든 경우의 수를 다 해보야한다. 최종 숫자에서 부터 1을 만들어갈 경우에는 +두개 전에 *하나가 있어야 된다는 제약을 통해 많은 경우를 줄일 수 있다. 따라서 최종 숫자에서 부터 줄여나가도록 했다. 먼저, 15를 예시로 시작해보자.
- 일단, 규칙상 마지막은 ++로 끝나므로 13++로 시작해도 무방하다.
- +가 두개 나왔으므로 ++ 왼쪽 수는 *를 하나 포함, 즉 3이상의 수여야 한다. (3 < 13)++
- 13은 3으로 나누어지지 않으므로 12+++가 되는 수 밖에 없다.
- 12는 3으로 나누어지므로 (9 < 11)++++로 가는 경우와 4*+++의 경우가 있다. 이 때, *++가 짝을 이루면 없애도 무방하다. [(9 < 11)++++, 4+]
- 11은 3으로 나누어지지 않으므로 (9 < 10)+++++가 되고 4도 3으로 나누어지지 않으므로 3++가 된다. 이 때, 3++은 ++과 같으므로 가능한 경우가 된다. (+*+++)
- 10은 3으로 나누어지지 않으므로 (27 < 9)++++++, + 6개면 왼쪽 수가 최소 (333 = 27) 이어야하는데 그 보다 작으므로 이 경우는 불가하다.
- 따라서 15를 만드는 경우는 1가지. 경우가 나누어지는 곳을 재귀함수로 구현하여 코딩하면 다음과 같다.
| #include <cmath> | |
| #include <stdio.h> | |
| int findCase(int n, int nPlus); | |
| // 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요. | |
| int solution(int n) { | |
| int answer = 0; | |
| return findCase(n - 2, 2); | |
| } | |
| int findCase(int n, int nPlus) { | |
| int result = 0; | |
| if (n < 1 || 2*log(n)/log(3) < nPlus) { | |
| return 0; | |
| } else if ( n == 3 && nPlus == 2){ | |
| return 1; | |
| } else if ( n == 3 && nPlus == 3) { | |
| return 0; | |
| } | |
| if (n % 3 == 0 && nPlus >= 2){ | |
| result += findCase(n / 3, nPlus - 2); | |
| } | |
| result += findCase(n - 1, nPlus + 1); | |
| return result; | |
| } |