[S5] 백준 1094번 막대기 node.js

⚡문제정보

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

1094번: 막대기

백준은 입력받는게 귀찮아보여서 멀리하고 있다가 입력받기 아하모먼트가 오면서

허겁지겁 문제를 푸는 중입니다. 가볍게 실버 5 문제 하나 풀어봤읍니다.

조건은 간단합니다 64보다 작은 자연수 X가 주어지고 그 자연수를 만들기위해 필요한 막대의 수를 구하면됩니다.

막대는 반드시 반으로만 자를 수 있는데 반으로 자른 막대의 길이가 X보다 작다면 막대 하나를 버립니다.

 

여기까지 이해가 되었다면 예제를 통해 생각해보는 것이 매우 쉬워집니다.

X = 23이라고 가정하고 수도코드를 작성해보면 다음과 같습니다.

---

🔍접근방법

X = 23 / 막대기 = 64

64cm의 막대기를 둘로 나누면
32cm, 32cm 막대기 두개가 된다.
32가 23보다 크다면 32cm 막대기 하나를 버린다.

따라서 수중에는 32cm 막대기하나만 있다.
다시 막대기를 반으로 가른다

32 /  2
수중에는 16 / 16 막대기가 있다.
16이 23보다 크다면 16cm 막대기 하나를 버린다
그러나 16은 23보다 작기때문에 아무 막대기도 버리지않는다.

16 / 2
수중에는 이제 16 / 8 / 8 막대기가 있다.

이런식으로 작성하면됩니다
뭔가... 생각나는게 있네요
코드로 옮겨보겠습니다.

---

😑나의 풀이

const fs = require("fs");
let input = +fs.readFileSync("/dev/stdin").toString()
let stick = 64
const arr = []
let count = 0
let answer = 0

if(input === 64) {
    console.log(1)
    return
}

while(stick>1) {
    if(stick === input) {
        console.log(1)
        return
    }
    stick = stick/2 
    if(stick > input) {
        arr.push(stick)
    }
    else {
        arr.push(stick)
        arr.push(stick)
    }
}

for(let i = 0 ; i < arr.length ; i ++) {
    if(input - count >= arr[i]) {
        count += arr[i]
        answer += 1
    }
    
    if(input - count === 0) {
        console.log(answer)
        return
    }

}

더 효율적으로 푸는 방법도 있을 것 같기는 한데

문제를 최대한 정직하게 옮겨서 풀어봤습니다.