boj 5624 : DOBRI

boj 5624 : DOBRI

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

삼성 코드그라운드의 좋은수 라는 문제와 유사하다.

N의 범위가 [-100000,100000]이라는 데서 힌트를 얻을 수 있다.

i번째 숫자가 세 수의 합으로 이루어져있는지 확인하기 위해서 일반적으로 코딩을 한다면 N^3으로 가뿐하게 시간초과가 나지만,

(i번째 숫자) - (i보다 먼저 오는 숫자)가 두 수의 합으로 이루어져있는지 확인하는 방법으로 코딩을하면 N^2만에 해결할 수 있다.

이 방법으로 해주기 위해 두 수의 합으로 이루어져있는지 확인하는 -100000~100000범위의 bool 배열을 이용한다.