[Programmers] 광물 캐기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

그리디 하게 접근한 문제입니다.

 

알고리즘은 아래와 같습니다.

1. 5개씩 구간을 끊고 다이아몬드, 철, 그리고 돌의 개수를 기록한 ore 구조체에 기록합니다.

2. 각 구간을 최소한의 피로도로 캐야 하므로 상위 광물이 많은 순서대로 성능이 좋은 곡괭이를 쓸 수 있도록 정렬을 했습니다.

2.1 즉, 다이아몬드가 많은 구간 > 다이아몬드 개수가 같다면 철이 많은 구간 > 다이아몬드, 철의 개수가 같다면 돌이 많은 구간

2.2 이 때, [ores.size() < total] 조건이 중요한데 이는 실제로 캘 수 있는 광물의 수가 주어진 광물의 수보다 적을 경우 처리를 위한 조건입니다. 

3. 정렬된 구간을 순회하며 남아있는 곡괭이 중 가장 성능이 좋은 곡괭이로 캤을 때 최적의 해를 구할 수 있습니다.

 

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~