[baekjoon] 백준 14247번(파이썬): 나무 자르기

문제

14247번: 나무 자르기

알고리즘

- 문제를 해석해보면 모든 나무를 한 번씩 자르는 게 최대 나무 양을 구하는 방법인 것을 알 수 있다.

- 나무의 초기 값과 나무가 자라는 수치를 2차원 리스트로 만들어 나무가 자라는 수치를 기준으로 오름차순 정렬한다.

- 나무가 자라는 수치가 작은 나무부터 자른다.

- 나무의 초기값과 나무가 자라는 수치 x 현재 날짜를 더한 값을 모두 더해 출력한다.

- 위 방법보다 더 효율적인 방법으로는 아래 설명에 있다. 

코드

(42976KB/120ms)

import sys

n = int(sys.stdin.readline())
h = list(map(int, sys.stdin.readline().split()))
a = list(map(int, sys.stdin.readline().split()))
temp = [[h[x], a[x]] for x in range(n)] # 반복문을 통해
temp = sorted(temp, key=lambda x: x[1])
answer = [temp[i][0] + (temp[i][1] * i) for i in range(n)]
print(sum(answer))

 

또 다른 풀이(36776KB/120ms)

import sys

n = int(sys.stdin.readline())
answer = sum(list(map(int, sys.stdin.readline().split())))
a = sorted(list(map(int, sys.stdin.readline().split())))
for i in range(n):
    answer += a[i] * i
print(answer)

코드를 모두 푼 후 다른 사람들에 코드를 보고 영감을 얻어 위 코드를 작성했다.

결국 모든 나무를 잘라서 더해야 한다면 나무의 초기 길이를 다 더한 후 나무가 자라는 수치를 정렬하여 날짜 - 1만큼 곱하면 된다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법