1-A

내 풀이(http://boj.kr/9635425d4767436c926250dd497800f2) - 맞음

공유 소스 보기

---

1-A

자 오늘은 백준 2309 일곱난쟁이 문제를 풀어보도록 할게요.

일곱난쟁이를 뽑아야 하는 문제입니다. 문제를 읽어보시면 순서와 상관없이 9개 중에 7개를 뽑는거죠. 그러면 순서와 상관없이 7개를 뽑는다? 9 Combination 7이죠.

그런데 사실 첫번째 풀이 방법은 9 Permutation 7로도 뽑을 수가 있어요. 물론, Permutation은 순서와 상관있이 뽑는 거죠. 근데 이 n 자체가 작기 때문에 원래는 Combination으로 뽑아야 되지만, Permutation도 가능해서 두 가지 방법을 모두 보여드릴 겁니다.

9 Permutation 7은 이렇습니다. 계산해보면 18만밖에 안되죠? 100만이나 400만? 한 1000만정도는 넘어가야 좀 많다라고 할 수가 있거든요? 그래서 '9 Permutation 7로도 할 수 있구나' 라는 걸 잡고 들어가는 거에요.

---

먼저, 첫 번째 방법입니다. Permutation을 이용할 건데, do-while(next_permutation)만 외우라고 했죠.

코드는 아래와 같습니다.

항상 next_permutation은 오름차순 배열을 기반으로 순열을 만든다고 했죠.

이 부분은 디버깅 코드입니다. 굉장히 간단하죠?

---

두 번째 방법은 9 Combination 7 입니다.

사실 9 Combination 7은 순서와 관계없기 때문에 그냥 7개를 뽑는 거죠. 9 Combination 7은 수학적으로 9 Combination 2와 같죠.

그러니까 정상적인 일곱난쟁이 7개를 뽑는 것과 비정상적인 일곱난쟁이 2개를 뽑는 것 둘 다 똑같은 로직이죠.

정상적인 일곱난쟁이 7개를 뽑아서 sum을 100을 만들거나, 아니면 이 모든 일곱난쟁이의 sum에다가 비정상적인 애 두 명의 키를 뺐더니 100인 거를 찾는 거랑 똑같은 로직이잖아요.

그래서 전체 합에서 두 명의 합을 뺀 것이 100이 되는 걸 찾으면 되는 거죠.

---

이제 코드를 보도록 하겠습니다.

일단은 전체 합을 구해야되기 때문에

이렇게 전체 합을 구했습니다. 그리고 나서, solve 함수를 볼게요.

combination 함수와 재귀함수를 교안에서 설명을 드렸어요. 그리고 개념 강의에도 설명을 드렸는데 재귀함수랑 중첩 for문을 생각하라고 했죠?

두개를 뽑는다 뭐? 중첩 for문 입니다.

sum에 두 원소의 합을 제외한 게 100일 때, pair 타입인 ret에다가 그 두 원소의 인덱스를 집어넣습니다.

그리고 이 두 원소에 걸리는 것들을 continue; 하고 나머지 원소들을 vector에 집어넣어요.

그리고 나서 오름차순으로 정렬하고 출력하면 됩니다.

이 두 개는 똑같은 for 문이에요. 위의 게 short cut 입니다.

 

자 다시 9개의 난쟁이 중에서 2명의 이상한 사람을 뽑는 조합의 로직을 살펴봤는데, 일단은 전체 합을 구해요.

'전체 합 - a - b가 100이 되는 로직으로 구현할 수 있겠구나' 라고 생각을 하시고 그 다음에 solve 함수를 들어가는 거죠.

두 명을 뽑는 거니까 중첩 for문을 쓴 거고, 조건에 맞는 애를 2개의 값을 집어넣을 수 있는 pair 에다가 집어넣고 return을 합니다.

그리고 나서, 가짜 녀석들을 거르고 진짜 녀석들만 담아서, 오름차순으로 정렬 뒤 출력하는 거죠.