빠에야는 개발중

생각했던 것 내림차순으로 각 요소를 정렬해서 사람 수만큼 하나씩 쭉 빼주다가 마지막 사람에게 전부 몰아주는 방법을 생각했다. 하지만 예제를 보면서 틀렸다는 걸 알았다. 맨 마지막에 남은 값들을 다 몰아주면 결과값이 선형적으로 증가할 것이기 때문이다. 그래서 수정한 방법은 꽃의 개수를 균일하게 가져갈 수 있도록 분배하는 것이었다. 꽃의 가격에 영향을 주는 것은 이전, 이후의 꽃의 가격이 아닌 "해당 꽃을 사는 사람의 이전 구매 개수"이다. 따라서 개수를 잘 조절하면 최소값을 얻을 수 있다. 진행 해시맵에 사람 수만큼의 원소를 넣고 내림차순 정렬한 꽃 배열을 순회하면서 순차적으로 해시맵의 구매 개수를 늘려준다. 개수를 매번 더해주면서 꽃의 가격도 함께 계산해준다. 여담 역시나 정렬을 기본으로 생각하니 생각하..

생각했던 것 important contest와 not important contest를 구분해서 저장해주면 연산하기가 훨씬 쉽다. 한꺼번에 넣어주면 다중 조건 정렬을 해줘야하기 때문이다. 진행 luck을 key라고 하고, 중요성을 value라고 두었을 때 value가 1인 것들을 따로 담아서 내림차순 한 다음, 받은 개수만큼은 앞에서부터 순차적으로 남겨두고 나머지 뒷부분은 전부 같은 절대값의 음수로 바꿔준다. 그리고 모든 리스트들의 값들을 더해주면 결과값이 나온다. 여담 그리디 알고리즘은 대부분 정렬로부터 시작되는 것 같다. 정렬을 내가 직접 구현하지 않아도 돼서 편하게 문제를 풀 수 있어 다행이다.

생각했던 것 절대값들 중 최소값을 찾는 문제로, 모든 경우의 수를 비교하여 최소값을 찾아내면 된다. 진행 ... 라고 하였으나 그러면 0(n^2) 시간에 끝날 것이기 때문에 비효율적이다. 경우의 수를 줄이기 위해서 생각한 것은 "정렬"이다. 예를 들어 오름차순으로 정렬했을때 [A, B, C] 배열이 도출되었다면 (A, B)의 차이는 (A, C)의 차이보다 작을 수 밖에 없다. 그러므로 모든 경우의 수를 따지지 않고, 바로 옆의 수와 비교하기만 하면 된다. 그러면 정렬하는 시간 O(nlogn) + 탐색시간 O(n)으로 O(nlogn) 시간 안에 끝낼 수 있다. 여담 각 수가 양수, 음수 여부에 따라 절대값 계산이 다를거라고 잠깐 착각했었다.. 그냥 뒷수에서 앞 수를 빼면 된다.