Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

백준 [14247] 나무 자르기 본문

코테준비/백준

백준 [14247] 나무 자르기

alstj_성공 2021. 5. 18. 16:45

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

 

나무 자르기 

2 초 512 MB 394 145 118 40.972%

문제

영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.

따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,

나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.

참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.

입력

첫째 줄에는 나무의 개수 n개가 있다.(1≤n≤100,000) 나무는 1번부터 n번까지 있다.

다음 줄에는 첫날 올라갔을 때 나무의 길이들 Hi가 n개가 순서대로 주어진다.(1≤Hi≤100,000)

그 다음 줄에는 나무들이 자라는 길이 Ai가 n개가 순서대로 주어진다.(1≤Ai≤10,000)

출력

영선이가 나무를 잘라서 구할 수 있는 최대 양을 출력하시오.

예제 입력 1 

5

1 3 2 4 6

2 7 3 4 1

예제 출력 1 

64

 

그리디 알고리즘과 정렬을 사용하는 문제

모든 나무를 자르는 것이 이득이므로

자라는 길이가 가장 작은 순으로 자르면 된다.

이 때, 답은 충분히 큰 숫자가 나올 수 있기 때문에 long long으로 해주어야 한다.

 

**그리디 알고리즘이란?

문제를 해결하는 과정 속에서 각 단계마다 가장 최선의 선택을 하는 방법

'코테준비 > 백준' 카테고리의 다른 글

백준 [21736] 헌내기는 친구가 필요해  (0) 2021.05.24
백준 [1004] 어린 왕자  (0) 2021.05.24
백준 2003 [수들의 합 2]  (0) 2021.05.07
백준 13699 [점화식]  (0) 2021.05.07
백준 14614 [Calculate!]  (0) 2021.05.07