목록2024/08/28 (1)
tlov
[swea] 1859. 백만 장자 프로젝트
문제: 1859. 백만 장자 프로젝트날짜: 08/28 (수)성공여부: O(댓글힌트) 그리디 문제이다. 그리디에 대한 준비가 안되어있어서 좀 어려웠다. 결론부터 말하면 배열을 뒤로 반복해서 풀면 풀리는 문제이다. 무조건 배열을 앞에서부터 반복할 필요가 없다는 생각을 해야한다.. 이게 참 쉬운데 어려운듯하다. 처음 풀이는 앞에서부터 반복하면서 현재 값에서 바로 뒤에 자기보다 작은 값이 나오면 현재 값을 기준으로 지금까지 산 물건들을 팔아 그 차액을 ret 변수에 더했다. 예제만 놓고보면 해당 로직에 문제가 없다. 그런데 아래 반례가 있다.1 2 3 5 2 4 7 11 2 3 5 2 4까지 모두 산다음에 7에서 팔면 최대 이익!그러나, 위의 로직대로 한다면 1 2 3 까지 산 후 5에서 모두 팔고, 다시 2 ..
알고리즘 문제
2024. 8. 28. 22:49