[BOJ-JS] 30076번 - Kalėdų senelis

30076번: Kalėdų senelis (acmicpc.net)

30076번: Kalėdų senelis

문제를 번역하자면,

- 산타가 아이들에게 선물을 나눠주려고 하고 있다! 아이는 총 N명.

- 그리고 은신처가 있다! 총 M개.

- 그렇다면 산타가 선물을 가지고 있어야 아이들에게 선물을 나눠줄텐데... 선물을 어떻게 준비하는지는 이후에 설명할 예정.

- N명의 아이들의 집에 순서대로 방문하면서 한 개씩 선물을 놓고 갈 것이며, 도중에 되돌아가서 선물을 다시 챙겨올 수 없다. 즉, 산타는 필요한 만큼의 선물을 잘 챙겨서 이동하면서 아이들에게 나눠주어야 한다.

- 은신처는 k_i번째 아이의 집 직전에 있으며, 은신처에는 선물이 z_i개 준비되어 있다.

- 산타는 처음 출발할때 몇 개든 상관 없이 마음껏 선물을 챙길 수 있고, 각 은신처에서 준비되어 있는 선물 중 원하는 만큼을 챙길 수 있다.

- 주어진 인풋의 첫 번째 줄은 N M이다.

- 이후 M개의 줄에 각각 k_i z_i 값이 주어진다. 이때 주어지는 k_i 값들은 오름차순이다.

- 산타는 들고 다니는 선물을 최소화 하려고 한다. 처음 출발할때, 그리고 각 은신처마다 몇 개의 선물을 챙겨야 할지 출력하시오(즉, 시작점과 은신처 M개를 합하여 총 M+1개의 줄에 각각 챙겨야 하는 선물 개수를 출력).

 

아이디어는 다음과 같다.

- 첫 번째 아이의 집부터 마지막 아이의 집까지, 만약 이후에 선물을 안 챙길 것이라면 현재 위치에서 총 선물을 몇 개 가지고 있어야 하는지 값을 배열로 만든다. 마지막 아이의 집에는 1개, 그 직전 아이의 집에는 2개, ... 이런 식으로 값이 들어있으면 된다. 이 배열을 p라고 하자.

- 뒤에 있는 은신처부터 시작해서, 여기서 총 몇 개의 선물을 챙기면 될지 결정해나간다. 마지막 아이의 집 직전에 은신처가 있는데 은신처에 100개의 선물이 준비되어 있다? 들고 있는 선물을 최소화 해야 하므로 1개만 챙긴다. 은신처에 있는 선물을 다 챙겨도 뒤에 있는 친구들에게 줄 선물이 부족하다? 그러면 선물을 다 챙기고, 앞선 은신처(혹은 출발지)에서 추가로 더 선물을 챙겨야 한다고 생각하면 된다. 즉, 챙겨야 하는 선물 개수 k는 은신처에 있는 선물 개수 z_i와 해당 위치에 확보되어야 하는 선물 개수 p[j] 두 값 중 작은 값이면 된다. 여기서 i, j라고 했는데 적당히 아무 인덱스나 넣은 것이고 코드를 보면 좀 더 잘 이해가 될 것이다.

- k값을 잘 보관해두자. 은신처에서 챙긴 선물 개수가 k라는 이야기니까 이후에 아웃풋으로 출력해야 한다.

- 은신처에서 선물을 챙겼으면 해당 위치를 포함해서 그 앞에 있는 위치들에 대해서 '챙겨야 하는 선물 개수' p[i]의 값에서 앞서 구한 k값을 빼준다. 왜냐하면 은신처에서 선물을 챙겼으니 앞서서 챙겨야 하는 선물 개수가 줄어들었으니까!

- 이런 논리로 필요한 선물의 개수를 계산해나가면 각 위치에서 챙겨야 하는 최소한의 선물 개수만 가져가면서 산타가 운반하는 선물 개수를 최소한으로 유지할 수 있다.

- 마지막에 p[0]값이 0이 아닐 수 있다. 그 얘기는 처음 출발할때 p[0]개의 선물을 챙겼어야 한다는 것. 출력할때 이 값부터 출력하자.

[a,...b]=(0+require('fs').readFileSync(0)).split`
`.map(i=>i.split` `.map(i=>+i))
p=Array(a[0]).fill(0).map((e,i)=>a[0]-i)
b=b.filter(i=>i[1]).reverse()
x=[]
b.map(i=>{k=Math.min(p[i[0]-1],i[1]);p.map((e,j)=>{if(j<i[0])p[j]-=k;});x.push(k)})
console.log([p[0],...x.reverse()].join`
`)