-
문제
https://www.acmicpc.net/problem/14247
14247번: 나무 자르기
영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어
www.acmicpc.net
문제에 대한 이해
밤마다 특정 길이만큼 빠르게 자라나는 n개의 나무 중 1개를 벨 때 n일동안 얻을 수 있는 최대 길이를 출력하라.
이해를 디테일하게
처음에는 하루하루 업데이트를 하면서, 그 날짜에 얻을 수 있는 최대의 값을 얻는 문제라고 생각을 하였다.
하지만 주어진 답과 맞지 않아서 고민을 해보니 "최대의 나무"를 얻기 위해서는 성장 속도가 긴 나무는 늦게 베어주는게 더 효과적 이라는 사실을 알게 되었다.
그리하여, 아래와 같이 베면 되겠다는 생각을 가지게 되었고
// 1 3 2 4 6 // 6 // 3 10 5 8 7 // 3 // 5 17 8 12 8 // 8 // 7 24 10 16 9 // 16 // 9 31 13 20 10 // 31
이를 간결하게 이야기 해보자면 성장 속도가 낮은 나무부터 벤다고 생각을 하면 될 것이다.
구현
성장 속도가 낮은 나무부터 베려고 한다면, 한번 정렬을 해주고 가는 것이 편하다고 생각을 하였다.
그리하여 주어진 성장 속도를 오름차순으로 정렬하고, 각 나무도 "성장 속도"에 맞게 정렬을 해주었다.
처음에는 각 날짜별로 모두 업데이트를 해줘야 한다는 생각에 날짜마다 모든 배열을 초기화 해주었다.
function solution() { let answer = 0; // 성장 속도를 오름차순으로 정렬 const newPerDay = perDay.slice().sort((a, b) => a - b); const new_trees = []; // 성장속도 - 나무의 짝을 찾아서, 배열에 담아주는 순회 for (let i = 0; i < newPerDay.length; i++) { // 기존의 성장 속도에 해당하는 인덱스를 찾아서 const idx = perDay.indexOf(newPerDay[i]); // 새로운 배열에 추가. new_trees.push(trees[idx]); } for (let i = 0; i < new_trees.length; i++) { answer += new_trees[i]; // 날짜마다 모든 배열을 업데이트 for (let j = 0; j < new_trees.length; j++) { new_trees[j] += newPerDay[j]; } } console.log(answer); }
하지만, 생각을 해보면 순서는 이미 정해져 있기 때문에 성장속도 * 요일을 곱해서 나무 길이에 더해주면 된다는 사실을 알게 되어 코드를 다음과 같이 수정 할 수 있었다.
function solution() { let answer = 0; const newPerDay = perDay.slice().sort((a, b) => a - b); const new_trees = []; for (let i = 0; i < newPerDay.length; i++) { const idx = perDay.indexOf(newPerDay[i]); new_trees.push(trees[idx]); } // 순서대로 정렬 했기 때문에, 날짜를 성장 속도에 곱해 준 다음 // 더하면 된다는 사실을 알게 되었음. for (let i = 0; i < new_trees.length; i++) { answer += new_trees[i] + newPerDay[i] * i; } console.log(answer); } const trees = [1, 3, 2, 4, 6]; const perDay = [2, 7, 3, 4, 1]; solution();
'PS > 백준' 카테고리의 다른 글
[ 백준 _ 13019 ] A를 B로 ( 그리디 - 자바스크립트 ) (0) 2021.07.07 [ 백준_17626 ] Four Squares ( DP _ 자바스크립트 ) (0) 2021.07.06 [ 백준_11256 ] 사탕 ( 그리디 - 자바스크립트 ) (0) 2021.06.29 [ 백준 -17609 ] 회문 ( 구현, 투포인터 - 자바스크립트 ) (3) 2021.06.29 [ 백준 - 19941 ] 햄버거 분배 ( 그리디 - 자바스크립트 ) (0) 2021.06.29 댓글