[백준/14247] 나무 자르기 - Python 파이썬

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

 

사용개념: 그리디

 

 

1. 최적해 구하는 방법?

현재 키와 성장률을 기준으로 각각 생각해본다.

• 당장 제일 키가 큰 나무를 선택한다 (X)
• 성장률이 작은 나무부터 선택한다 (O)
  
  • 모든 나무는 최대 n일 동안 성장할 수 있다. 따라서 나무마다 하루 성장하고 잘릴 수도, n일 동안 성장하고 잘릴 수도 있다.
  • 그렇기 때문에 하루에 성장할 수 있는 길이가 가장 긴 나무를 제일 마지막에 자르는게 최대로 나무를 자를 수 있는 방법이다.
  • 성장률이 제일 큰 나무만 계속 자르면 안되나?
    • 다른 나무들의 초기 길이를 자를 수 없다.

 

2. 나무를 성장률에 따라 정렬하기

# 나무를 성장률에 따라 정렬
trees = []
for i in range(n):
    trees.append([growth[i], height[i]])
trees.sort()

 

 

3. 성장률이 작은 나무부터 선택

# 성장률이 작은 나무부터 선택
answer = 0
for i in range(n):
    answer += trees[i][0] * i + trees[i][1]

 

초기 나무 길이 + i일까지 성장한 길이를 더해준다.

 

 

전체코드

n = int(input())
height = list(map(int, input().split()))
growth = list(map(int, input().split()))

# 나무를 성장률에 따라 정렬
trees = []
for i in range(n):
    trees.append([growth[i], height[i]])
trees.sort()

# 성장률이 작은 나무부터 선택
answer = 0
for i in range(n):
    answer += trees[i][0] * i + trees[i][1]
    
print(answer)

 

자바 코드

import java.util.*;
import java.io.*;

public class Main
{        
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        Long answer = 0L;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            answer += Long.parseLong(st.nextToken());
        }

        int[] growth = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            growth[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(growth);
        for (int i = 0; i < n; i++) {
            answer += growth[i] * i;
        }
        System.out.println(answer);
    }
}