728x90
프로그래머스, 광물캐기
📜문제
https://school.programmers.co.kr/learn/courses/30/lessons/172927
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분류 : accepted
📜풀이
처음 문제를 봤을때, 무조건 곡괭이를 순서대로 다 써야하는 줄 알았다.
# [dia, iron, stone]
picks = [0, 2, 1]
다이아몬드 곡괭이 없으니, 넘어가고 철 곡괭이로 10번 광물 캐기, 돌 곡괭이로 5번 광물 캐기
❌ 잘못된 풀이
from collections import deque
# [dia, iron, stone]
picks = [0, 1, 99]
minerals = ["diamond", "diamond", "diamond", "diamond", "diamond", "diamond"]
# 피로도
degree_of_fatigue = [
{'diamond' : 1, 'iron' : 1, 'stone': 1},
{'diamond' : 5, 'iron' : 1, 'stone': 1},
{'diamond' : 25, 'iron' : 5, 'stone': 1},
]
queue = deque(minerals)
def total_fatigue():
fatigue = 0 # 피로도 초기값
for i in range(len(picks)):
pick_cnt = picks[i] # 곡괭이 갯수
for _ in range(5 * pick_cnt): # 해당 곡괭이로 광물 5개 캘 수 있음.
if queue:
mineral = queue.popleft() # target 광물
fatigue += degree_of_fatigue[i][mineral]
else:
return fatigue
return fatigue
result = total_fatigue()
print(result)
이 코드로 제출했을때 test case 2, 5,6,7, 11,12,13,14,15, 24, 25, 26, 27, 28, 29, 34, 35 불통!
너무 많은 불통에, 이건 로직자체가 이상하다.. 직감..ㅠ
[질문하기]로 이동해 다양한 반례를 넣어봤지만, 답이 나옴... ;;;;당황
🎈 그러다 발견한 글!
반례, 문제 잘못 이해.
사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
예를 들어, [3,3,3]의 곡괭이가 있다고 합시다.
그리고 처음에 다이아몬드 곡괭이를 고르고 5번 캤다고 합시다. 그러면 [2,3,3]의 상태가 될 것입니다.
그러면 다음 번 고를 수 있는 곡괭이는 무엇일까요? 위 상태에서는 모든 곡괭이가 가능합니다!!!
즉, 다이아몬드를 골랐다고 해서 끝까지 다이아몬드를 고를 필요는 없는 것입니다.
따라서 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다. 라는 규칙은, 5번 사용을 지키라는 규칙이지
곡괭이 종류에 관한 규칙은 아닙니다.
문제를 다시 보니, 최소한의 피로도로 광물을 캐려고 합니다. + 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.
이 조건만 있을뿐... 문제를 내식대로 해석했다.
결국 여러 곡괭이를 사용해서 광물을 캐고 그중 피로도가 가장 작은 방식으로 캐면 되는 거였다!
완전탐색, dfs(재귀함수)로 풀면 되는 문제였다.
✅ 올바른 풀이
# [dia, iron, stone]
picks = [0, 1, 1]
minerals = ["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]
# 피로도
degree_of_fatigue = [
{'diamond' : 1, 'iron' : 1, 'stone': 1},
{'diamond' : 5, 'iron' : 1, 'stone': 1},
{'diamond' : 25, 'iron' : 5, 'stone': 1},
]
total_f = []
def total_fatigue(idx, d_pick, i_pick, s_pick, f):
if idx >= len(minerals) or (d_pick == i_pick == s_pick == 0):
total_f.append(f)
return
d_f = 0
i_f = 0
s_f = 0
for i in range(idx, min(idx + 5, len(minerals))):
d_f += degree_of_fatigue[0][minerals[i]]
i_f += degree_of_fatigue[1][minerals[i]]
s_f += degree_of_fatigue[2][minerals[i]]
if d_pick:
total_fatigue(idx+5, d_pick-1, i_pick, s_pick, f+d_f)
if i_pick:
total_fatigue(idx+5, d_pick, i_pick-1, s_pick, f+i_f)
if s_pick:
total_fatigue(idx+5, d_pick, i_pick, s_pick-1, f+s_f)
total_fatigue(0, picks[0], picks[1], picks[2], 0)
print(total_f)
print(min(total_f))
📜 제출용 풀이
def solution(picks, minerals):
degree_of_fatigue = [
{'diamond' : 1, 'iron' : 1, 'stone': 1},
{'diamond' : 5, 'iron' : 1, 'stone': 1},
{'diamond' : 25, 'iron' : 5, 'stone': 1},
]
total_f = []
def total_fatigue(idx, d_pick, i_pick, s_pick, f):
if idx >= len(minerals) or (d_pick == i_pick == s_pick == 0):
total_f.append(f)
return
d_f = 0
i_f = 0
s_f = 0
for i in range(idx, min(idx + 5, len(minerals))):
d_f += degree_of_fatigue[0][minerals[i]]
i_f += degree_of_fatigue[1][minerals[i]]
s_f += degree_of_fatigue[2][minerals[i]]
if d_pick:
total_fatigue(idx+5, d_pick-1, i_pick, s_pick, f+d_f)
if i_pick:
total_fatigue(idx+5, d_pick, i_pick-1, s_pick, f+i_f)
if s_pick:
total_fatigue(idx+5, d_pick, i_pick, s_pick-1, f+s_f)
total_fatigue(0, picks[0], picks[1], picks[2], 0)
return min(total_f)
😂 반성
문제의 의도를 잘 파악하고 분석하는 과정을 거치자!
그냥 바로 풀려고 하니, 이런 잘못된 접근을 하게 되는 것 같다.
'알고리즘' 카테고리의 다른 글
백준, 뱀 (0) | 2023.10.11 |
---|---|
프로그래머스, 게임 맵 최단거리 (0) | 2023.09.25 |
백준, 최소 비용 구하기 (0) | 2023.09.01 |
프로그래머스, 키패드 누르기 (0) | 2023.08.23 |
프로그래머스, 숫자짝궁 (0) | 2023.08.21 |