[Boj/백준] 14247 Python

문제출처: https://www.acmicpc.net/problem/14247

14247번: 나무 자르기

 

 

1. 문제 접근 방식

두 개의 리스트를 한 개의 리스트로 묶고 grow가 작은 순서대로 정렬하고

tree + grow * i의 값을 sum에 더해주는 방식을 생각했다.

 

 

2. 내가 푼 코드

import sys

case = int(sys.stdin.readline())

tree = list(map(int,sys.stdin.readline().split()))
grow = list(map(int,sys.stdin.readline().split()))

arr=[]
for i in range(case):
    arr.append((tree[i],grow[i]))

arr.sort(key=lambda x:(x[1]))
sum=0
for i in range(case):
    sum+=arr[i][0]+arr[i][1]*i

print(sum)

 

 

3. 결과 및 느낀점

전형적인 그리디 문제인 것 같다.

tree와 grow 리스트를 다시 arr 리스트에 append하는 것은 비효율적인 것 같은데

대체할 수 있는 알고리즘을 생각해 보는 것이 필요하다.

리스트의 원소가 n,m 형태일 때 lambda 함수를 사용하면 쉽게 정렬할 수 있다.