(Python/🥇3)백준알고리즘 5624번: 좋은 수

 

문제 바로가기 

좋은 수

문제:

정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

입력:

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ Ai ≤ 100,000)

출력:

첫째 줄에 좋은 수의 개수를 출력한다.

 

풀이: 

 

요즘 추세는 DP 인거 같아서 혼자 문제를 풀 때에는 DP만 푸려고 한다.

 

이 문제는 i 번째의 수가 i 앞에있는 3개의 숫자의 합으로 이루어 지는데 중복이 가능하다.

그러면 

A+B+C = I 가 되어야하는데

N 이 5000개 이므로 5000^3 이면 탈락이다.

그럼 A+B = I-C 형태로 만들어 주면 된다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
a = list(map(int, sys.stdin.readline().split(" ")))

sets = set()
sets.add(a[0] + a[0])

count = 0

for x in range(1, n):
    for y in range(x):
        if a[x] - a[y] in sets:
            count += 1
            break

    for y in range(x+1):
        sets.add(a[x] + a[y])
print(count)

 

맨 처음 숫자의 2개의 합을 넣어준다

 

그러면 a[x] - a[y]  in sets 의 의미가

A + B = a[x] - a[y]  가 된다.

만약에 가능한경우 count += 1 을 해주고

 

또 다른 A+B의 값을 만들어서 sets 에 담아주는 식으로 진행했다.