[백준 JS] 1703번 생장점

문제

branchorama 나무는 특이한 규칙을 가지고 성장합니다. 어린 branchorama 초목은 하나의 잎을 꼭대기에 가진 가는 묘목이며, 그 잎에는 생장점이 있습니다. 성장하는 계절 동안 나무의 생장점들은 여러 개의 가지로 나뉘게 되며, 성장이 끝나면 각 가지는 생장점을 가진 하나의 잎을 꼭대기에 매달게 됩니다. 놀랍게도 같은 나무의 모든 생장점들은 같은 숫자(splitting factor)의 가지로 나뉘며, 그 숫자는 해가 지남에 따라 변합니다.

아래의 예는 Brown 씨의 과수원에서 한 branchorama 나무가 유목에서부터 3년간 자란 결과를 보여줍니다.

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

예시에서 예측할 수 있듯이, branchorama 나무는 과밀하게 성장하는 경향이 있습니다. 따라서 Brown 씨는 매 겨울마다 과도하게 성장한 나무들의 가지를 쳐냅니다. 아래는 가지를 쳐낸  branchorama 나무의 예입니다

branchorama 나뭇잎은 굉장히 크고 광합성에 유리하지만, 오직 생장점이 온전히 보존된 가지의 끝에만 달립니다. 따라서 나무가 버티지 못할 정도로 가지를 쳐내는 일은 없어야 합니다.

Brown 씨는 각 나무가 몇 개의 잎을 가졌는지 알고 싶어합니다. 나뭇잎을 일일이 세는 것은 지루하기 때문에, 각 해(level) 성장기의 splitting factor와 그 해 겨울에 쳐낸 가지의 수를 이용해 Brown 씨에게 나뭇잎의 수를 알려주세요.

 

 

입력

입력의 각 줄은 하나의 branchorama 나무를 의미합니다.

각 줄은 나무의 나이 a(1 ≤ a ≤ 20)로 시작하며, 그 뒤로 2a 개의 정수가 공백을 두고 주어집니다. 2a 개의 정수는 splitting factor와 가지치기 한 가지의 수가 level 별로 나열된 것입니다.

마지막 줄로  '0'이 주어지며 더 이상의 입력은 없습니다. '0'은 처리하지 않습니다.

 

 

출력

각 나무에 대하여 나무에 달려있는 잎의 수를 한 줄씩 출력하세요. 나뭇잎의 수가 signed 32-bit integer를 초과하지 않는다고 가정해도 좋습니다.

 

 

풀이

생장점은 분할, 가지치기를 반복했을 때 최종적으로 남은 가지의 숫자를 구하는 문제다.

 

잎의 수를 출력하라고 하지만 가지치기를 당하지 않은 나무만 추가로 확장되며

가지치기를 하지 않은 나무만 최종상태에서 잎이 달린다고 하기 때문에

결론적으로는 가지의 숫자를 구하는 것이 맞다.

 

출력 조건은 다행히 적당한 범위 안에 있다고 하는 것 같기 때문에 BigInt를 사용하지는 않아도 되는 문제로

각각의 케이스를 받아온 다음 

년수가 지날 때 마다 초기값 1로 세팅된 가지의 숫자에 분할될 숫자를 곱해준 다음

가지치기할 숫자를 빼고 다음 년도로 넘어간다.

 

최종적으로 년도가 끝난 다음 result에 결과를 담아주고 모든 케이스가 끝난 경우 출력해서 해결했다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')

const result = []

for(let i = 0 ; i < input.length-1 ; i++){
    const eachCase = input[i].split(' ').map(Number)
    let leafNumb = 1
    for(let j = 1 ; j < eachCase.length ; j += 2){
        leafNumb *= eachCase[j]
        leafNumb -= eachCase[j+1]
    }
    result.push(leafNumb)
}

console.log(result.join('\n'))

const input = `1 3 0
2 3 0 2 0
3 3 0 2 0 2 0
3 3 0 2 1 2 3
2 4 1 3 4
4 5 0 5 1 5 2 5 101
0`.split('\n')

const result = []

for(let i = 0 ; i < input.length-1 ; i++){
    const eachCase = input[i].split(' ').map(Number)
    let leafNumb = 1
    for(let j = 1 ; j < eachCase.length ; j += 2){
        leafNumb *= eachCase[j]
        leafNumb -= eachCase[j+1]
    }
    result.push(leafNumb)
}

console.log(result.join('\n'))