[백준] 18111번 마인크래프트 _ Node.js

 

문제

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

18111번: 마인크래프트

 

---

문제 풀이

 해당 문제는 문제가 길지만 정리하면 간단한 수학 문제이다. 땅을 캐는데는 2라는 시간이 소모되고, 땅을 채우는데는 1이라는 시간이 소모된다. 이 때 땅을 채우기 위해서는 인벤토리에 땅 블록이 있어야지만 가능하다.

 

 문제는 최대 층에서 최소층까지 진행하며 해당 층을 만들기 위해서는 얼마의 시간이 필요한지 확인하면 된다.

x라는 층을 만들기 위해서는 x보다 높은 블록을 제거하고, x 보다 낮은 층을 채워야한다. 이 때 제거한 블럭 + 기존 인벤토리의 땅 블록 개수가 채워야하는 블록보다 작을 경우는 해당 층을 제작할 수 없다.

 

 해당 과정에서 overblock과 shortblock으로 각 블록을 저장하고 이를 연산하며 가장 짧은 소요 시간을 출력해준다.

 

 

변수 선언

let [h,w,inven] = input().split(' ').map(Number);	
let map = [];
// 가장 높은 층과 낮은 층을 구하기 위해 최대 최소 층을 반대로 선언 및 초기화
let highist = 0;
let shortist = 256;
//계산 층의 초과 블럭 수와 부족 블록 수 변수 선언
let overBlock = 0;
let shortBlack = 0;
//층과 answer 선언 및 초기화
let floor = 0;
let answer = [Number.MAX_VALUE,0];

 

데이터를 가지고 오는 동시에 최상층과 최하층을 구한다.

for(let i = 0; i < h; i++) {
    const v = input().split(' ').map(Number)
    const max = Math.max(...v);
    const min = Math.min(...v);
    if(max>highist)  highist = max;
    if(min<shortist)  shortist = min;
    map.push(v);
}

 

가장 높은 층에서 시작하여 각 층의 초과 블럭과 부족 블럭을 구하고 가지고 있는 블록 수가 클 경우 소요 시간을 계산하고 이를 answer과 비교한다.

floor = highist;
while(floor >= shortist){
    overBlock = map.reduce((a,y)=>{
        const yValue = y.reduce((b,x)=>{
            if(x - floor > 0)
                return b + (x - floor);
            else
                return b
        },0)
        return a + yValue;
    },0)

    shortBlack = map.reduce((a,y)=>{
        const yValue = y.reduce((b,x)=>{
            if(floor-x > 0)
                return b + (floor-x);
            else
                return b
        },0)
        return a + yValue;
    },0)
    if(inven + overBlock >=  shortBlack){
        const cost = overBlock*2 + shortBlack
        if(answer[0] > cost)   answer = [cost,floor];
    }
    floor--;
}

console.log(answer.join(' '));

 

+++++

 

 

이 때 어차피 map을 두번 reduce를 쓰는 것 보다 한번에 하는 것이 좋을거라 판단하여 아래 코드로 변경을 해보았는데 시간 초과가 나왔다.

--> 왜지??

floor = highist;
while(floor >= shortist){
    [overBlock,shortBlack] = map.reduce((a,y)=>{
        const yValue = y.reduce((b,x)=>{
            const over = x - floor > 0 ? x - floor : 0;
            const short = floor-x > 0 ? floor-x : 0;
            
            return [b[0] + over, b[1] + short]
            
        },[0,0])
        return [a[0] + yValue[0],a[1] + yValue[1]];
    },[0,0])

    // shortBlack = map.reduce((a,y)=>{
    //     const yValue = y.reduce((b,x)=>{
    //         if(floor-x > 0)
    //             return b + (floor-x);
    //         else
    //             return b
    //     },0)
    //     return a + yValue;
    // },0)
    if(inven + overBlock >=  shortBlack){
        const cost = overBlock*2 + shortBlack
        if(answer[0] > cost)   answer = [cost,floor];
    }
    floor--;
}

console.log(answer.join(' '));

 

제출 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`3 4 99
0 0 0 0
0 0 0 0
0 0 0 1`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();


let [h,w,inven] = input().split(' ').map(Number);
let map = [];
let highist = 0;
let shortist = 256;
let overBlock = 0;
let shortBlack = 0;
let floor = 0;
let answer = [Number.MAX_VALUE,0];


for(let i = 0; i < h; i++) {
    const v = input().split(' ').map(Number)
    const max = Math.max(...v);
    const min = Math.min(...v);
    if(max>highist)  highist = max;
    if(min<shortist)  shortist = min;
    map.push(v);
}


floor = highist;
while(floor >= shortist){
    overBlock = map.reduce((a,y)=>{
        const yValue = y.reduce((b,x)=>{
            if(x - floor > 0)
                return b + (x - floor);
            else
                return b
        },0)
        return a + yValue;
    },0)

    shortBlack = map.reduce((a,y)=>{
        const yValue = y.reduce((b,x)=>{
            if(floor-x > 0)
                return b + (floor-x);
            else
                return b
        },0)
        return a + yValue;
    },0)
    if(inven + overBlock >=  shortBlack){
        const cost = overBlock*2 + shortBlack
        if(answer[0] > cost)   answer = [cost,floor];
    }
    floor--;
}

console.log(answer.join(' '));