[역추적검색(Backtracking) | JavaScript] 10810 공 넣기

https://prpn97.tistory.com/72

[Baekjoon | JavaScript] 10810 공 넣기

**위 링크에 해당 문제가 있습니다.

조건에 따라 배열의 요소를 갱신하고 이전 요소는 상관이 없어지는 문제를 푸는데,

애초에 그 값을 구하지 않아도 되는데 굳이 반복을 하는 부분이 있다고 생각이 들었다.

 

문제로 예를 들어 순서대로 풀게 되면 다음과 같다.

3  3 0 0 0

3  3 4 4 0

1  1  1  1 0

1  2  1  1 0

 

3과 4를 처음에 추가하지만, 결과값인 1 2 1 1 0에 3과 4는 없다.

총 4번의 과정을 거치게 된다. 

그렇다면, 거꾸로 값을 추적해서 맨 마지막에 갱신한 것을 처음에 갱신하고,

갱신이 되었다면 더 이상 바꾸지 않는다면 과정을 줄일 수 있다고 생각했다.

const fs = require("fs");
let input = fs.readFileSync("./input.txt").toString().split('\n')
let len = input[0].split(' ').map(Number)
let arr = new Array(len[0]).fill(0)

for (let i = input.length - 1; i >= 1; i--) {
  let num = input[i].split(' ').map(Number)
  for (let j = num[1] - 1; j >= num[0] - 1; j--) {
    if(arr[j]===0){
        arr[j] = num[2]
    }
  }
}
let answer = arr.join(' ')
console.log(answer)

이렇게 하게 되면, 기본적으로는 값을 반대로 추적한다.

3 - 4 - 1 - 2를 순으로 더하는 것이 아니라, 2 - 1 - 4 - 3을 순으로 더한다.

그러나 더할 때 기본적으로 배열 arr은 0으로 채워져 있기 때문에

arr의 요소가 0일 경우에만 조건을 수행하도록 했다. 

이 조건이 없다면 0 2 0 0 0 에서 1 1 1 1 0이 되고,

1 1 4 4 0을 거쳐 3 3 4 4 0이 결과가 된다. 

당연히 더한 순서만 바뀐 것이기 때문에 4번의 과정을 거치게 된 것이다.

 

조건을 수행하게 된다면, 0 2 0 0 0에서 1 2 1 1 0 이 된다.

반복문을 돌면서 끝인 4번 인덱스를 갱신하는 부분은 입력값에 없기 때문에 

총 2번의 과정만 거치게 된다.