[백준] 16235번: 나무 재테크 - python

문제 출처

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

 

 

 

---

 

풀이 & 코드

 

python으로 해당 문제를 풀 때 핵심은 시간을 최소화 하는 것이다. 실제로 필자는 처음 제출에 시간 초과로 실패했다.

 

푸는 방식은 간단하다. 특별한 알고리즘 보다는 단순 코딩으로 문제에서 요구하는 바를 구현해주면 된다. 필자는 현재 양분, 추가될 양분의 양들을 2차원 배열에 각각 저장했다. 나무의 경우 2차원 배열로 위치를 지정해주고 해당 위치에서의 나무들을 나타내기 위해 1차원 배열을 사용해 총 3차원 배열을 이용했다. N의 크기가 최대 10으로 작았기에 가능했다.

 

처음 제출에서 시간 초과가 발생해 줄이기 위해서 나무들을 나타낸 1차원 배열을 deque로 바꾸어 주었다. 작은 나무부터 양분을 주기 위해선 sort하는 과정이 필요한 데, deque에 있는 appendleft 매서드를 이용하면 O(1)에 해결 되기 때문에 deque를 이용했다.

 

 

 

 

추가로 필자에게 도움이 되었던 TestCase들이다.

5 2 7
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 1 3
3 2 3

# 답 : 71

100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
1 1 1 

# 답 : 5443

 

 

 

 

해당 문제는 삼성 기출문제로 solved.ac 에서는 GOLD-3 에 랭크되어 있다.