백준 2746: 좋은 배열 만들기 (Python)

문제링크

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

문제 총평

- 케이스를 잘 생각해 낸다면 쉬웠던 문제

문제 접근방식

- 이번 문제는 처음에 접근을 너무 어렵게 해서 많이 틀렸습니다.

- 하지만 단순한 경우의 수라는걸 알면 쉽게 풀 수 있습니다.

정답코드

import sys; input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
s = sum(arr)
ans = 0
s1 = s-arr[-1]
num = [0] * (1000000+1)
for i in arr:
    num[i] += 1
num[arr[-1]] -= 1
for i in set(arr[:-1]):
    if s1-i-arr[-1] >= 0 and s1-i-arr[-1] <= 1000000 and num[s1-i-arr[-1]]:
        if s1-i-arr[-1] == i:
            ans += num[s1-i-arr[-1]] * (num[s1-i-arr[-1]]-1)
            continue
        ans += num[s1-i-arr[-1]] * num[i]
ans //= 2
num[arr[-2]] -= 1
s2 = s1-arr[-2]
if s2-arr[-2] <= 1000000 and s2-arr[-2] >= 0:
    ans += num[s2-arr[-2]]

if s2-arr[-3] == arr[-3]:
    ans += 1
print(ans)

1. 먼저 가능한 경우는 3개로 생각할 수 있습니다.
2. 첫번째. 배열의 최대 값(arr[-1])이 나머지 배열의 합에서 두 원소를 제거한 값과 같을 경우
3. 두번째. 배열의 최대 값을 빼고(arr[-1]) 두 번째 최대값(arr[-2])이 나머지 배열의 합에서 한 원소를 제거한 값과 같을 경우
4. 세번째. 배열의 최대 값 두개(arr[-1],arr[-2])를 빼고 나머지 최대값(arr[-3])이 나머지 배열의 합과 같은경우
5. 첫번째의 경우에는 전체 합에서 최대값을 빼고 남은 전체 합에서 두 원소를 뺀 값이 최대값과 같은 경우입니다. -> 이 경우 전체 순회를 하면서 현재 순회 중인 값 i + j(전체 - 최대값 - i) 의 갯수 두개를 곱하면 됩니다.
6. 하지만 i,j가 같은 경우에는 nC2 이므로 n*(n-1) 을 해줍니다. (마지막에 //2를 할것이므로 여기서는 //2를 안해줌)
7. 그렇게 구한 모든 경우의 수를 2로 나눠줍니다. (전체를 돌면서 같은 경우를 두번씩 체크하므로)
8. 두번째의 경우 전체합에서 최대값과 두번째 최대 값을 뺀 값이 특정 요소를 뺀 전체 값과 같으면 되므로 s2-arr[-2]를 세줍니다.
9. 세번째의 경우에는 전체값-첫번째최대값-두번째최대값 = 세번째 최대값이 되면 됩니다.

문제 풀이 후 생각

- 풀이를 좀 더 간소화 할 수는 있지만 이게 명확해 보여서 3가지 경우를 나눴습니다.

- 그리고 원소의 최대값이 1000000 이므로 불가능한 경우를 조건 처리 해줬습니다.

- 수학적인 지식이 부족한게 느껴지네요... 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요