백준 11051 이항 계수2

2017.11.01 ** 수요일 ** Solution - 11051(이항 계수2)
백준 11051 이항 계수2

풀이방법: 동적계획법

문제 해석

이항 계수 문제이다. 고등학교때 수학을 배웠다면, 쉽게 생각할 수 있다.

단 .. 기억을 하고있다면 ...

역시 나는 기억하지 못하고 있었다(공부는 못해도 수학은 좀 했다 신승범짱!)

네이버 검색을 해서 이항계수의 공식을 보는데 이렇게 풀면 되겠구나 하는게 있었다.

출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

이 공식을 보고 풀이를 시작했다.

풀이방식

한번 생각해보자 ,
우리는 n과 k를 안다.
두가지로 나눠져있다.

=> 두개의 경우로 나눠서 합치자!

순열,조합을 풀다보면 항상 재귀를 떠올리게 된다.

이것 또한 재귀적 방법으로 풀면된다. 또한 메모이제이션을 통해 효율성을 높여주면된다.

그리고 공식에서는 우측이 n+1이지만, 우리는 굳이 저렇게 할필요없다. 모든 항목을 -1해주자

이제 끝이다. 뽑기만 하면된다.

그리고 베이스 케이스 설계를 해야되는데, 한 번 생각을 해보자, 뽑을때마다 각 케이스 별로 -1씩을 해줄것이다.

dp {n}[k} = solution(n-1,k-1) + solution(n-1,k);

이렇게 식을 세우게 되면 어느순간 k==n 또는 k==0이된다. 수학시간에 배웠다. nCn =1 , nC0 = 1이다.

그러면 우리는 베이스 케이스를 설계 할 수 있다.

if(n==k||k==0) return 1;

이렇게 설계하면 될 것이다.

그리고 메모이제이션

if(dp{n}{k}>0) return dp{n}{k}

이제 끝이다 !

이렇게 3줄이면 끝난다. 검증을 하고 싶다면 예제를 손으로 하면된다. 5분도 안걸린다.
코드 전체 보기

: 나이를 먹더니 수학을 다 까먹은 것 같다..