코딩테스트 입문 - 구슬을 나누는 경우의 수 ( 조합, 재귀 )

 

이러다가

하루에 4개나 블로그를 쓸까 봐 걱정이다.

ㅋㅋㅋㅋㅋ

너무 어려워서 마음고생 시간 쓰고

다음에도 또 풀 수 있으면 좋겠다마는..

 

희망만 안고 출발

 

---

 

3C2 이거 아닌가?

거 뭔가 3! / 2!인데

이게 음..

for문으로 하면 글자수가 터진다. 30 개인게 위험하다.

 

인지 씨에게 효율적인 풀이를 물었다.

 

5C3의 경우

5 *4 * 3 / 3 * 2 * 1

이니까

그냥 하나씩 계산하라고 했다.

 

즉 5를 곱하고 1로 나누고

4를 곱하고 2로 나누고

3을 곱하고 3으로 나누라는 것이다.

 

오 이게 가능한가?

이러면 막 숫자가 이상하게 나눠지지 않을까 생각했다.

반대로 5를 곱하고 3을 나누면 숫자가 이상해지듯 말이다.

그래서인지 씨는 말한다.

 

조합에서는

기적같이 항상 나누어 떨어지긴 하는데

순서가 이상하면 안 된다고

꼭!

1부터 나눠줘야 한다고.

 

 

짜잔..!

 

 

힝..

문제가 뭘까..?

코드는 꽤 완벽에 가까운걸??

 

이라고 했지만 인지 씨는

int의 크기 때문이라고 지적했다.

 

answer에서 balls 곱하는 과정에서 순간

21억을 넘을 수도?! 있으니

처음에 int로 하는 거보다 

answer값을 크게 long long으로 잡으라는 것이다.

 

눼눼

 

아니!!!!!!!

 

이 문제가 뭘까를 따라가 보면 이랬다.

 

사실 for문에서 share값을 <=으로 수정하려고 했다.

 

근데 

 

< 이렇게 해도 테스트가 통과되길래

 

아 <=가 아니라 < 이거구나

하며 넘겼다.

 

하지만 이건 그냥 운이 좋았던 것일 뿐...

 

ㅋㅋㅋㅋㅋㅋㅋ..

쳇..

 

 

이렇게 해야! 모든 테스트가 맞아서

정답이 된다!!

 

테스트를... 너무 믿지 말자

 

---

 

 

 

ㅎㅋㅋ 나는 사실 인지 씨의 도움과 5C3을 어떻게 풀지

대충 감을 잡았어서 푼 건데..

 

재귀함수를 쓰는 거 같기도 하다 왜냐하면..

! 이거 뭐 힌트라고 줬었다.

 

재귀로 푼다면

함수를 만들고

글자 두 개를 넣는다.

 

int combi(int b, int s)

여기서 b는 balls

s는 share

 

5C3 예시로

1. 내가 뽑히는 경우

나는 뽑혔으니 4명 중 2명만 더 데려와

(b-1, s-1)

 

2. 내가 안 뽑히려는 경우

나는 빼고 4명 중에 3명만 골라

(b-1, s)

 

이 두 가지를 더해야 한다.

왜냐면 모든 경우의 수니까!!

 

그리고 골라야 할 예외상황

 

1. 구슬이 없을 때

( share값이 0일 때 ) 아무것도 안 고르는 법 = 1

 

2. 구슬이 하나밖에 없을 때

( ball값이 1일 때 ) 한 개 밖에 없으니 = 1

 

3. 구슬의 개수가 같을 때

그것도 한 번이면 된다! = 1

 

 

완성!

 

피곤하다.. 풀어서 좋긴 한데...

피곤하다...ㅎㅎㅋ 시간이..