[파이썬] 백준 5624 : 좋은 수 (골드 3)

[파이썬] 백준 5624 : 좋은 수 (골드 3)

5624번: 좋은 수

---

문제

---

풀이

방향성 생각

• 입력이 5000이라 N^2까지 가능
• 처음 풀이는 순회 하면서 모든 조합을 저장해서 조회하는 식으로 했는데 시간 초과
• 현재 숫자 a에서 이전에 arr에서 등장했던 숫자 o를 빼면 a-o가 나온다.
• 이 a-o가 이전에 두 숫자의 조합으로 만들 수 있으면 그 숫자을 카운팅
• 경우의 수가 아니라, 각 위치에 있는 숫자가 좋은 수인지만 판별하면 된다.

전체코드

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

one,two = set(),set()
dp = [False]*n

for i in range(n):
    a = arr[i]
    for o in one:
        if a-o in two:
            dp[i] = True

    one.add(a)
    for o in one:
        two.add(a+o)

print(sum(dp))

 

코멘트

.