1-J

내 풀이(http://boj.kr/0d07091dbacf433abed781c2915bee19) - 틀림

공유 소스 보기

---

1-J

1-J, 백준 9375 문제를 풀어보도록 할게요.

일단은 이 문제 예시 해석부터 해볼까요?

hat이랑 turban이랑 이렇게 있죠. 얘네들을 headgear이죠. 그리고 sunglasses가 있어요. 얘네는 eyewear죠. 이렇게 했을 때 어떤 경우의 수가 나오죠?

예시 출력이 5인데요, 어떻게 5가 되는지 한번 보도록 하겠습니다.

일단 hat만 쓰는 경우, turban만 쓰는 경우, sunglasses만 쓰는 경우가 있죠.

그리고 hat과 sunglasses, turban과 sunglasses 이렇게 2가지가 있죠. 그래서 총 5가지입니다.

근데 생각해보면 이 이름 자체가 필요 없다는 생각이 혹시 드시나요?

지금 headgear가 2개이고, eyewear이 1개 잖아요. 그래서 이름과는 상관없이 headgear는 그냥 동그라미로, eyewear은 세모로 놔도 사실은 상관이 없는 거죠.

그래서 이런 식으로 매칭해도 된다고 생각이 드는 거예요.

그러면 일단은 이 이름 자체가 필요 없기 때문에 종류만, 종류에 해당하는 counting을 하는 거죠.

그럼 2와 1을 기반으로 해서 어떻게 하면 5가 나올까?

생각해보면 얘가 동그라미가 있고 동그라미가 없는 경우의 수가 있지 않을까요? 또한 세모가 없는 경우의 수가 있지 않을까요?

무슨 말이냐면,

그러니까 이 동그라미 하나만 있는 경우는 이 동그라미를 입을 때 세모를 입지 않는 경우의 수죠. 그럼 실제적으로는 hat 하나만 쓴 거예요.

그럼 이제 이거를 다 곱한 다음에 아무것도 안 입은거, 즉 x끼리 매칭된 것만 빼면 되지 않을까? 라고 생각하고 들어가시는 거예요.

자 이 문제는 경우의 수 문제인데, 잠깐 경우의 수에 대해서 좀 설명을 해드릴게요.

제가 어떤 코인에 투자를 했어요. 잃을 수도 있고 딸 수도 있죠. 성공 확률이 50%예요.

그 다음에 제가 이어서 또 코인에 투자를 하는데, 또 50%의 확률로 성공을 합니다.

자 그러면은 여기서 질문,

이 코인과 이 코인이 같이 오를 확률은 몇 퍼센트? 25%죠.

0.5 x 0.5 = 0.25 인 거죠. 경우의 수는 곱하기입니다.

직접 세어봐도, 같이 상승, 같이 하락, A는 상승 B는 하강, A는 하강 B는 상승 이렇게 4분의 1, 즉 25%죠.

그래서 아까 문제에서,

3 x 2 한 다음에 아무것도 안 입는 경우의 수인 1을 제외해서 5가 나온 겁니다.

도식화하면 이렇게 나타낼 수 있겠네요.

---

자 코드를 한번 보도록 하겠습니다.

먼저, a와 b 즉 이름과 종류를 입력받죠. 그런데 우리한테 필요한 건 종류니까

이렇게 counting을 합니다. 동그라미랑 세모 개수를 세는 거죠.

그 다음에

map을 순회하면서 카운트 한 개수를 + 1해주고 곱해주죠. + 1을 왜 해준다고요? 종류별로 아무것도 안 입는 경우의 수를 하나 더 세어주는 거죠.

지금 보면 ret을 long long으로 선언해줬죠? 여러분 경우의 수 문제에서는 수가 좀 커질 수가 있습니다. 그래서 이건 팁인데, 앞으로 경우의 수 문제라고 하면은 그냥 long long을 받고 시작하는 게 좋습니다.