고양이는 많을수록 좋다.(백준 코딩테스트 27961번, 그리디, NodeJS 풀이)

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

27961번: 고양이는 많을수록 좋다

 

문제 수준:

브론즈1

 

 

문제 요약:

좋아하는 애니메이션 등장인물이 나와서 낚여서 푼 문제이다.

마법소녀 마도카의 목표는 고양이 N마리를 생성하는 것이다.

마도카가 쓸 수 있는 마법은

• 고양이 1마리 늘린다.
• 현재 있는 고양이 수의 일부 또는 전체를 복사한다. (현재 있는 고양이가 M 마리일 때 1~M 마리 복사)

목표 N마리가 주어졌을 때 최소 몇 번의 생성마법으로 만들 수 있는가?

 

 

입출력 예 (입력 / 출력):

 

문제 풀이 전략:

1. 처음 0마리일땐 2번째 마법을 쓸 수 없다. 처음에는 꼭 1마리 추가마법을 써야한다.

2. 1마리 추가마법을 쓴 다음에는 2번째 마법만 쓰는게 가장 빠르게 숫자를 늘릴 수 있는 방법이다.

3. 결국 최대로 늘릴 수 있는 만큼 계속 생성하다가 N을 넘어서는 순간이 가장 최소 횟수이다. (1~M마리 추가 마법을 반복하여 목표에 도달할 수 있는 경우)

 

내 풀이:

let fs = require("fs");
let goal = +fs.readFileSync("input.txt").toString(); // 목표 N마리

let cnt = 0; // 횟수 세기
let cats = 0; // 현재 고양이
while (cats < goal) { // 목표보다 현재 고양이가 적다면
  if (cats === 0) { // 현재 고양이가 0일때는
    cats++; // 고양이를 1마리 추가한다.
    cnt++; // 횟수도 올린다.
  } else { //나머지는
    cats = cats * 2; // 최대 복제마법을 계속 쓴다.
    cnt++; // 횟수도 올린다.
  }
}
console.log(cnt); // while문을 탈출한 직후가 최소 생성 횟수.

마도카가 고양이를 구하기 위해서 마법소녀가 됐다는 썰에서 착안해서 만든 문제인거같다.