BOJ :: [5624] 좋은 수

문제

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

5624번: 좋은 수

 

문제 요약

좋은 수 문제는 주어진 숫자들 중에서 i번째 수 보다 앞에 있는 수 3개를 더해 i번째 수를 만들 수 있다면 i번째 수를 좋은 수라고 한다. 즉, a + b + c = d를 만족하는 d가 몇 개인지를 구하는 문제이다. d보다 앞에 있는 수 중 3개를 뽑는 조합을 모두 구하려면 O(N^3)으로 주어진 문제의 N의 개수가 5000으로 시간 초과가 발생한다. 따라서 수식을 a + b = d - c로 변형시켜 a + b값을 저정해 놓고 d - c값이 존재하는지만 판별은 방법으로 시간 복잡도 O(N^2)으로 문제를 해결할 수 있다.

 

풀이

두 수를 더해서 나오는 수의 중복을 없애기 위해 set을 이용하여 수를 저장하고 d - c가 set에 존재하는지를 확인하는 방법으로 구현했다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
s = set()

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

result = 0
s.add(arr[0] + arr[0])

for i in range(1, n):
    for j in range(i):
        if arr[i] - arr[j] in s:
            result += 1
            break
    
    for j in range(i+1):
        s.add(arr[i] + arr[j])

print(result)

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다 . 질문도 환영합니다! :)