13305 주유소

• 유형: 그리디

• 풀이방식: 먼저 현재 주유소와 다음 주유소의 리터당 가격을 비교하면 다음과 같이 두 가지의 상황이 발생한다.

  1. 현재 주유소가 다음 주유소의 가격보다 더 비쌈
  2. 현재 주유소가 다음 주유소의 가격보다 더 저렴

  1번의 경우 현재 주유소에서 다음 주유소로 갈 수 있는 양의 최소한의 기름만 구매하고, 2번의 경우는 현재 주유소 가격으로 다음 주유소에서 다다음 주유소로 가야할 거리의 기름까지 구매하면 된다. |

  즉 내림차순으로 진행된다고 생각했을때 내림차순이 아닌 경우가 발생되면 이전의 경우를 덮어쓰면 된다.

  8 9 7 10 2 3 → 8 8 7 7 2 2

  위의 경우에서 각 주유소 사이의 거리를 2 3 4 3 3이라고 한다면 최소 비용은

  (8 * 2) + (8 * 3) + (7 * 4) + (7 * 3) + (2 * 3) = 95가 된다.

1758 알바생 강호

• 유형: 정렬, 그리디
• 풀이방식: 뒷 순번으로 진행될수록 제외되는 팁의 값이 오름차순으로 정렬되므로 큰 수를 앞에 두어야 한다. 즉 배열을 내림차순으로 정렬하고 아래의 계산을 진행하면 된다.
• 팁 - (받는 순서 - 1)

11508 2 + 1 세일

• 유형: 정렬, 그리디
• 풀이방식: 3개를 묶어사면 세 품목 중 가장 저렴한 품목을 무료로 제공해준다. 즉, 어차피 가장 비싼 품목은 할인받을 수 없고, 최대한 비싼 품목끼리 묶어야 큰 할인을 받을 수 있다는 점을 생각하면 간단하게 풀 수 있다.

내림차순으로 정렬한 후 순서대로 3개씩 묶어가면 가장 큰 할인폭으로 물건을 구매할 수 있다.

20115 에너지 드링크

• 유형: 정렬, 그리디

• 풀이방식: 가장 많은 양의 에너지 드링크에 나머지 드링크들을 부어주면 최대의 에너지 드링크 양을 만들 수 있다.

  간단하게 정렬 및 반복문으로 풀 수 있었음