1-L

내 풀이(http://boj.kr/0e1bbad28cfe4278ad664446b391d49b) - 맞음

내 풀이(http://boj.kr/68ae5b799c3340dab050fc532e0fb146) - 맞음

공유 소스 보기

---

1-L

오늘은 1-L 1940 주몽 문제를 풀어보도록 하겠습니다.

이 문제는 최대 15,000개인 N개의 재료가 주어져요.

그래서 이 재료 중에서 두 개를 고르는 거죠. 그리고 이 재료는 각각의 고유한 번호를 가지고 있어요. 이 번호는 10만 이하의 번호를 가지고 있죠.

그래서 N개의 재료 중 두 개를 선택해서 이 두개의 번호의 합이 M개인 것을 찾는 거죠. 즉, M이 되는 것이 몇 개인지 counting을 하는 문제인 겁니다.

어떻게 해야될까요?

주어진 재료 중에서 두 개를 고르는 것, 뭐죠? Combination(조합)이죠. 재료를 고를 때 순서가 상관이 없죠. 순서가 상관이 있으면 Permuation, 순서가 상관 없으면 Combination 라고 말씀드렸어요.

순서가 상관없이 재료 두 개를 고르는 거기 때문에, N개 중에서 2개를 고르는 nC2가 된다는 거예요.

그런데 이 if 문은 뭘까요? m이 20만보다 더 크다면 0을 출력하고 그게 아니라면 로직을 짜는 거죠.

고유한 번호는 10만 이하라고 했으니까 두 개의 재료를 선택해서 더한 합이 20만을 초과하지는 않을 거예요.

그래서 사실 if 문은 없어도 되지만 시간초과 때문에 시간 단축을 위해서 적은 것입니다.

이제 else문 안에 있는 로직을 보면, 제가 세 개까지는 중첩 for문을 통해서 Combination을 구현하라고 말씀을 드렸죠.

이렇게 하면 됩니다.