/programmers

2017 Kakaotalk 예선 4단 고음

2017년도 카카오톡 코딩테스트 예선 문제인 4단 고음을 풀어보았다.


문제 링크 : 아이유 4단고음

1에서 시작해서 (*++) 를 적절히 조합해서 최종 숫자를 만드는 방법의 수를 구하는 문제이다. 1부터 시작해서 *와 +를 조합해가면서 최종 숫자를 만드려면 최종숫자보다 큰 수가 나올 때 까지 모든 경우의 수를 다 해보야한다. 최종 숫자에서 부터 1을 만들어갈 경우에는 +두개 전에 *하나가 있어야 된다는 제약을 통해 많은 경우를 줄일 수 있다. 따라서 최종 숫자에서 부터 줄여나가도록 했다. 먼저, 15를 예시로 시작해보자.

  1. 일단, 규칙상 마지막은 ++로 끝나므로 13++로 시작해도 무방하다.
  2. +가 두개 나왔으므로 ++ 왼쪽 수는 *를 하나 포함, 즉 3이상의 수여야 한다. (3 < 13)++
  3. 13은 3으로 나누어지지 않으므로 12+++가 되는 수 밖에 없다.
  4. 12는 3으로 나누어지므로 (9 < 11)++++로 가는 경우와 4*+++의 경우가 있다. 이 때, *++가 짝을 이루면 없애도 무방하다. [(9 < 11)++++, 4+]
  5. 11은 3으로 나누어지지 않으므로 (9 < 10)+++++가 되고 4도 3으로 나누어지지 않으므로 3++가 된다. 이 때, 3++은 ++과 같으므로 가능한 경우가 된다. (+*+++)
  6. 10은 3으로 나누어지지 않으므로 (27 < 9)++++++, + 6개면 왼쪽 수가 최소 (333 = 27) 이어야하는데 그 보다 작으므로 이 경우는 불가하다.
  7. 따라서 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;
}
view raw solution.cpp hosted with ❤ by GitHub

Jaeyoun

Jaeyoun

The maintainer

Read More