1109: 자라나라 나무나무

Link : judge.koreatech.ac.kr/problem.php?id=1109

---

1. 문제

• A 행성에는 "자라나라 나무나무" 라는 이름의 나무가 있습니다. 이 나무 씨앗은 목수들에게 아주 귀한 건축 재료 인데, 그 이유는 씨앗을 심은 다음 날, 무려 몸통의 길이가 1m인 나무가 되며, 그다음 날부터는 전날의 두 배의 길이가 되기 때문입니다. 단, 단점이 있다면 이러한 특징이 있는 만큼 매우 비싸며, 몸통이 매우 단단하여 자르는 비용이 상상을 초월한다는 점입니다. 그나마 다행인 건 몸통을 제외한 뿌리와 가지들을 자르는 건 쉽다는 점이지요.
  하여튼, 이러한 성질 때문에 나무를 자르지 않고 이어 붙이는 방법으로 이 나무가 사용되고 있습니다.
  예를 들어, 3m 길이의 기둥을 만들 때는 첫째 날에 나무 한 그루를 심고, 둘째 날에 나무 한 그루를 심습니다. 셋째 날에는 첫째 날 심은 나무는 2m 길이의 나무가 되고, 둘째 날 심은 나무는 1m 길이의 나무가 되어서, 두 개를 붙여 3m 길이의 나무 기둥을 만들 수 있습니다.
  여러분은 이 목수를 도와, 되도록 적은 양의 나무 씨앗으로 길이 L의 기둥을 만드는 방법을 알려주려고 합니다.
  L 길이의 나무를 만드는데, 몇 개의 씨앗과 몇 일째에 심으면 되는지 출력하는 프로그램을 만들어 주세요.

 

---

2. 문제의 조건

• 1 <= L <= 1,000,000,000

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 케이스가 10억이라 O(sqrt(N))이내의 시간에 풀면 얼추 답이 나온다고 생각하였습니다.

 

• 아이디어
  
  1일엔 1, 2일엔 2, 3일엔 4, 4일엔 8, 5일엔 16 ... 즉 이를 나타내면 다음과 같습니다.
  
  

  1

  2

  4

  8

  16

  32

  64

  128

  256

  512

  이 말은 1일에 심은 나무가 5일이 지나면 16m가 된다는 의미입니다.
  이를 이용하면 어렵지 않게 구할 수 있습니다.
  
  즉, O(1) 시간에 해결할 수 있습니다.
  
  

 

---

4. 풀이 방법

• 최대값이 1,000,000,000이므로 2^n < 10억 까지 값을 구해줍니다.
• 총 29까지 생기며 10억을 넘지 않는 2^n은 536,870,912인 것을 알 수 있습니다.
• 29부터 target을 빼주며 짤라진 idx와 처음으로 짤라진 cut_day를 기록합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/59

 

---

 

cjw.git@gmail.com