https://www.acmicpc.net/problem/18185
18185번: 라면 사기 (Small)
라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ��
www.acmicpc.net
딱 보자마자 그리디인건 알았는데
코너케이스랄까 조금 예외가 되는 케이스가 있어서
많이 고생했던 문제
라면을 하나 가져올때보다 두개 같이사는게 싸고
두개보다 세개를 살때가 더 싸므로
그리디로 생각했을때 가장 먼저 생각나는 풀이는 그냥
살수있는만큼 최대한 사는거였다.
그런데 질문창에도 있는 대표적인 반례인 1 2 1 1 같은 경우에서는,
세개 사고 0 1 0 1 이 되어
총가격이 13이 되지만,
두개사고 세개사는 경우에는
1 2 1 1 -> 0 1 1 1 -> 0 0 0 0 으로 12만에 살 수 있다.
이걸 판별해주기위해서 ramen[i+1] > ramen[i+2]라는 조건을 주고
두개를 먼저사도록 짰으나 WA.
그래서 두개를 먼저 사야하는것은 1 2 1 1 의 케이스에서 볼 수 있고,
두개를 사는 갯수에 따라서 최적해가 바뀔수 있었다는 생각이 들었기 때문에
두개를 몇번 묶어사야하는가에 초점을 두고 고민하기 시작했다.
그 결과 2 3 2 1 에서 반례를 발견!!
두개 묶어 최대한 사는 경우는
2 3 2 1 -> 0 1 2 1 -> 0 0 1 0 -> 0 0 0 0 으로 20의 가격이 필요하지만,
두개묶은걸 한번만 사는 경우는
2 3 2 1 -> 1 2 2 1 -> 0 1 1 1 -> 0 0 0 0 으로 19라는 최소값이 나올 수 있었다.
위와같은 반례를 몇개 찾아본 결과
ramen[i]과 ramen[i+1]-ramen[i+2]. (위에서 ramen[i+1]이 더 큰지 확인했기때문에 항상 양수이다)
둘중 작은 값이 두개 묶어 살때 몇번 사는지를 결정할 수 있다는 사실을 알아냈고
그대로 구현했다.
그리고 결과는 깔끔하게 AC.
*** 다이아 문제 검열됨 ***
직접 풀어봅시다!처음으로 풀어낸 다이아 문제라 그런지
성취감이 장난 아니다
이 재미에 PS 계속 하는거 같다
오늘 잠은 편히 잘 수 있겠다 ㅋㅋ