문제 상황을 파악하기 위해서 여러번 시뮬레이션 하다보면 기존의 Amart 위치에 Imart를 짓는 것이 가장 유리하다는 것을 파악할 수 있다. 이때 우선적으로 선택되는 Imart의 위치는 다음과 같다. 예를 들어 Amart가 1 3 5위치에 놓여있다고 하자. 만약 3번을 선택했을 때 얻을 수 있는 사람의 수는 (1~3 사이의 사람의 수 / 2 + 1~3사이의 사람의 수 % 2) + 자기자신 + (3~5 사이의 사람의 수 / 2 + 3~5 사이의 사람의 수 / 2)라는 것을 파악할 수 있다. (단, alpha는 0 or 1) Amart 사이에 Imart가 놓이게 될 경우, 거리가 더 가까운 위치의 mart를 가게 되므로 사이의 위치한 사람의 수 / 2가 골라지는 것은 자명하다. 다만, 추가적으로 modul..

문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다. 문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들이 구매할 수 있게끔 최적(?)의 방법으로 구매하는 것이 가장 이득이라는 것을 간파할 수 있다. 즉, 이 지점에서 그리디 문제가 아닐까 의심을 해볼 수 있다. 직관적으로 잘 생각해보면 마스크를 제일 많이 팔 수 있는 경우는 해당 마스크 가격에만 구매할 수 있는 사람을 최우선적으로 구매권을 주면 된다는 것을 간파할 수 있다. 즉, 이 문제를 풀기 위해서는 각 상점을 기준으로 해당 가격 마스크를 시민들의 구매할 수 있는지 여부를 체크하고 그 중 가장 최적의 케이스 순서대로 구매를 진행해야 한다. 다만, 이 문제에서 입력값이..