[코딩테스트][SWEA] 🔥 SWEA 14510번 "나무 높이" 문제: Python으로 완벽 해결하기! 🔥
문제 링크
🕒 Python 풀이시간: 1시간 50분
for tc in range(1,int(input())+1):
answer=0
N=int(input())
arr=list(map(int,input().split()))
maxH=max(arr)
needed=dict()
needed[1]=0
needed[2]=0
for i in range(N):
k=maxH-arr[i]
needed[2]+=k//2
needed[1]+=k%2
minTwo=min(needed[1],needed[2])
answer=minTwo*2
needed[2]-=minTwo
needed[1]-=minTwo
if needed[1]>0:
answer+=needed[1]*2-1
else:
t=needed[2]*2
if t%3==0:
answer+=t//3*2
else:
answer+=t//3*2+t%3
print("#"+str(tc)+" "+str(answer))나무 키우기: 가장 높은 나무에 맞춰라! 🌳💧
물을 주어서 가장 높은 나무 높이에 나머지 나무 높이를 맞추는 문제이다. 쉬워보이지만 어려운 문제였다. 그리디에서도 어려운 편이 아닐까?...
N개의 나무에서 가장 큰 나무를 찾아준다. 그리고 우리가 필요한건 각 가장 높은 나무에서 나머지 나무들을 빼서 키워야되는 나무높이 이기 때문에 이 수를 구해준다. 문제는 여기 부터이다. 나무를 키우기 위해서는 1,2로 2일이 걸리기 때문에 3일로 나눠줘서 찾아야한다고 생각하기 쉽지만 전혀 그렇지 않다. 1짜리로 2의 높이를 완성시킬 수 있기 때문이다.
그렇기 때문에 먼저 한번 2로 나누어서 없애주어야 한다. 즉, 2로 나누어서 먼저 2가 만들어지는 갯수, 그리고 1이 만들어지는 갯수를 구해서 겹치는 갯수 만큼 2일씩 사용하여 정답에 더해준다. 그런 다음 사용한 만큼 1과 2의 갯수에서 빼준다. 그러면 이제 진짜로 1만 남던지 2만 남는다. 이렇게 되면 이제 정답과 거의 다왔다.
1은 2로 만들 수 없기 때문에 단순히 2일씩 사용한 후 마지막에는 1일만 사용해도 되므로 -1을 해준다. 2의 경우는 먼저 2를 곱해서 구해야되는 원상 길이로 복구 시켜준다. 그러면 이 길이를 가지고는 3으로 나눌 수 있다. 왜냐하면 1로도 2로도 되는 길이 이기 때문이다. 그렇기 때문에 3으로 나누어떨어지면 그대로 그 수에 2를 곱해서 정답을 더해주고(1,2해서 2일씩 걸리기 때문) 3으로 나누어떨어지지 않으면 3으로 나눈 답에 추가 일자, 즉 3으로 나눈 나머지를 더하면 일자가 나온다.
이렇게 Python로 SWEA의 "나무 높이" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
