[백준 14247번] 나무 자르기 - (java,python)

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

 

📌 문제 탐색하기

 

가장 성장률이 높은 나무를 가장 마지막에 잘라야 나무의 길이를 가장 많이 얻어 갈 수 있다.

따라서 가장 성장률이 낮은 나무부터 먼저 자르면 된다.

 

📌 코드 설계하기

성장률을 기준으로 정렬을 한 뒤, 매일 하나씩 잘라주면 된다. 

생각해보니 모든 나무를 자르기 때문에 나무 초기 길이는 따로 저장할 필요가 없어서 바로 answer 변수에 더해주었다.

성장률의 경우 배열에 저장을 한 뒤에 오름차순 정렬을 하고 날짜마다 곱해준 값을 answer에 더해주면 된다.

 

📌 코드

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//int[] trees = new int[n];
		int[] growth = new int[n];
		int answer = 0;

		for (int i = 0; i < n; i++) {
			answer += sc.nextInt();
		}

		for (int i = 0; i < n; i++) {
			growth[i] = sc.nextInt();
		}

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

		System.out.println(answer);

	}

}

 

Python

import sys
input = sys.stdin.readline

n = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))

ans = 0

# 초기 나무 크기 전체
ans += sum(H)

A.sort() # 오름차순 정렬

for i in range(n):
    ans+= A[i]*i

print(ans)