IT 개발 돼지의 일상

SWEA 1859. 백만 장자 프로젝트 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc) "완전 탐색할 건 아니야, 뭔가 아이디어를 찾자." 해당 문제에서 N이 1,000,000 까지가 있고, 각 지점에서 할 수 있는 행동은 산다/판다/아무것도 안한다. 의 세가지로 나뉜다. 따라서 대략적인 시간복잡도를 계산해 보면 3^1,000,000 이 되고, 완전 탐색으로는 시간 내에 풀 수 없다. 따라서 다른 아이디어를 찾아야 했다. 주식 그래프를 생각해보자. 언제 파는 것이 이익이 최대가 될까? 당연히 고점 보다 낮게 사서 고점에 파는것이 좋다. 고점을 그래프의 가장 끝점으로 우선 잡는다. 내..