[백준] 28250 이브, 프시케 그리고 푸른 MEX의 아내 (python 파이썬)

https://www.acmicpc.net/problem/28250

28250번: 이브, 프시케 그리고 푸른 MEX의 아내

---

문제 이름이 특이해서 풀어본 문제. 실2라고 얕잡아봤다가 끔찍한 결과가 나왔다.

실제 코테였다면 풀었을지 장담 못하겠다. 꼭 입력값 제한을 보면서 시간을 추측하는 습관을 들이자.

 

여담이지만 코테 환경을 상상하며 문제를 푸는 건 도움이 되는 거 같다.

---

아이디어

1. 이중 for문 실패

• 수식을 보고 무식하게 이중 for으로 구현했다가 시간초과했다.

2. 일반화

• mex라는 함수의 특징으로 식을 구할 수 있다.
• 일단 mex의 값은 0, 1, 2로 정해져있다.
• 0은 Ai, Aj가 둘다 0이 아닌경우
• 2은 Ai, Aj의 값이 각각 0, 1인 경우
• 1은 나머지 경우([0, 0] 일때, [0, 1보다 큰수] 일때)
• 위의 조건을 가지고 코드로 구현하면 된다. 

---

전체 코드

N = int(input())

arr = list(map(int, input().split()))

arr_count_0 = arr.count(0)
arr_count_1 = arr.count(1)

#Sum = arr_count_0 * arr_count_1 * 2  + (N - arr_count_1 - arr_count_0) * arr_count_0 + (arr_count_0 * (arr_count_0 - 1) // 2)

Sum = arr_count_0 * (arr_count_1 * 2  + N - arr_count_1 - arr_count_0 + ((arr_count_0 - 1) / 2))

print(int(Sum))

*Sum값은 주석에 있는 식을 줄인것

---

코드 설명

arr_count_0 = arr.count(0)
arr_count_1 = arr.count(1)

일단 원하는 값을 구하기 위해 배열에서 0의 개수와 1의 개수를 미리 구해준다.

Sum = arr_count_0 * arr_count_1 * 2  + arr_count_0 * (N - arr_count_1 - arr_count_0) + (arr_count_0 * (arr_count_0 - 1) // 2)

조합이 [0, 1]인 경우 mex값이 2 이므로 'arr_count_0 * arr_count_1 * 2' 로 작성했다.

조합이 [0, x(x > 1)]인 경우 mex값은 1이다. 따라서 'arr_count_0 * (N - arr_count_1 - arr_count_0)'로 작성했다.

조합이 [0, 0]인 경우 mex값은 1이다. 따라서  '(arr_count_0 * (arr_count_0 - 1) // 2)'로 작성했다.

mex값이 0인 경우는 당연히 무시해도 된다.

 

제출할 때는 수식을 공통인수 arr_count_0로 묶어서 제출했다. 

---