키큰개발자

문제사이트 : http://codeup.kr/problem.php?id=1925

해결 방법 :

nCr을 구하기 위해서 생각해보면, 

n개 중 r개를 뽑는 것은  

n개 중 먼저 하나를 보는데 이게 뽑혀져있는 상황에서 r-1개(하나가 먼저뽑혓다)를 뽑는 경우 + n개 중 하나를 먼저 보는데 이게 안뽑혀있는 상황에서 r개를 뽑는 경우의 수랑 같다는 것을 아는 것이 이 문제를 푸는 핵심인것 같다.

이제 이를 이용해서 점화식을 세운다면, 

 가 된다.

이식을 바탕으로 재귀함수를 디자인하면 된다.

기저조건은 r 부분이 0이 되거나 혹은 n과 r이 같을 때 이 두가지로 나눌수있다.

기저조건이 아닐때는 점화식대로 재귀함수를 호출해주면 된다.

<해결 방법>

이 문제는 정수 n 을 입력받아서 2진수로 출력하는 문제이다.

예를들어 12라는 숫자가 입력되면 

1100 이 출력되면된다.

이 문제를 재귀함수로만 풀어야 하는 조건이 있기때문에 재귀적인 패턴을 먼저 찾아야한다.

우리가 일반적으로 2진수를 변환할때를 생각해보면, 12를 일단 2로 쭊쭉쭉 계속 나눠본후 나머지를 거꾸로 이어서 붙여주면 2진수가 완성된다.

이때, 12를 2로나눠서 생긴 나머지에 2로나눈 몫인 6을 다시 2로 쭉쭉쭉 나눠서 생긴 나머지와 붙여준다면 2진수가 완성된다.

이걸 그림으로 표현해 보면 다음과 같다. (그림 잘 못그림 ㅜ)

이걸보면 재귀적 패턴을 알수있다.  

string getBinaryNum(int n) : n을 입력받아 2진수를 반환하는 함수  라고 정의를 한다면, 

getBinaryNum(n/2) + (n % 2)  <- 이 식의 의미는 현재 n의 2를 나눈 나머지를 n/2로 나눈 숫자의 2진수를 반환하는 것에 갖다 붙인다. 즉, 원래 n에 대한 2진수를 반환할 수 있게된다. 

요약하자면 재귀함수가 n/2에 대한 2진수를 반환해줄거니까 우리는 이거에 현재 n을 2로나눈 나머지만 갖다가 붙이면 되는것이다.