16434 드래곤 앤 던전 node.js

24.10.10 기준 속도 1등

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

백준에서 이분탐색 문제집을 차례로 풀고 있었는데, 만난 문제입니다.
근데, 문제를 읽다보니 이게 왜 이분탐색이지..? 라는 생각이 들었습니다.

이분탐색..?

이분탐색인 이유는 매 던전의 방에 입장할 때 마다, 필요한 최소의 hp를 구해야 합니다. 이 때 모든 hp를 완전탐색으로 할 수 없기 때문에 이분탐색으로 최소의 hp를 구하는 방법입니다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input/16434.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [len, initialAtk] = input.shift().split(' ').map(Number);
const stages = input.map(stage => stage.split(' ').map(Number));

function checkATK(maxHP) {
  let playerHP = maxHP;
  let playerATK = initialAtk;
  for (let [type, atk, hp] of stages) {
    if (type === 1) {
      const attackTurns = Math.ceil(hp / playerATK);
      const damageTurns = attackTurns - 1;
      const totalDamage = BigInt(damageTurns * atk);

      if (playerHP <= totalDamage) return false;

      playerHP -= totalDamage;

    } else if (type === 2) {
      playerHP = maxHP > playerHP + BigInt(hp) ? playerHP + BigInt(hp) : maxHP;
      playerATK += atk;
    }
  }
  
  return playerHP > 0n;
};

let start = 1n;
let end = BigInt(len) * 1000000n * 1000000n;
let mid;
let ans;

while (start < end) {
  mid = (start + end) / 2n;

  if (checkATK(mid)) {
    ans = mid;
    end = mid;
  } else {
    start = mid + 1n;
  }
}

console.log(ans.toString());

그리디

용사는 무적이라고 생각하고, 모든 공격을 다 맞으면서 전진한 다음 가장 hp가 낮았을 때 +1을 하면 그게 답 아닐까?

const fs = require('fs');
const file = process.platform === 'linux' ? 'dev/stdin' : '../stdin.txt';
const [temp, ...tempArr] = fs.readFileSync(file).toString().trim().split('\n');
const [N, atk] = temp.split(' ').map(Number);

let user = { hp: BigInt(0), atk: BigInt(atk) };
const arr = tempArr.map((el) => el.split(' ').map(Number));
let minHp = BigInt(0);

arr.forEach((el) => {
  const [type, a, h] = el;
  const atk = BigInt(a);
  const hp = BigInt(h);
  if (type === 2) {
    if (user.hp + hp > 0) user.hp = BigInt(0);
    else user.hp += hp;
    user.atk += atk;
  } else {
    let cnt = hp / user.atk - BigInt(1);
    if (hp % user.atk !== BigInt(0)) cnt += BigInt(1);
    user.hp -= atk * cnt;
  }
  minHp = minHp < user.hp ? minHp : user.hp;
});

console.log(String(-(minHp - BigInt(1))));

결과적으로 node.js기준으로 현재 1등인 코드입니다.
그냥 수식적으로만 접근하면 풀 수 있었던 것 같아요.

1.포션일 때

유저의 공격력을 올리고,
유저의 체력을 회복시키는데, 0보다 커지면 0으로 수정합니다.

2. 몬스터일 때

용사의 공격력이 3이고 몬스터의 hp가 100, 공격력이 3이라고 가정해보면

• 몬스터는 용사에게 34번 공격당해야 죽음
• 따라서 용사는 몬스터에게 33번 공격당함

BigInt는 Math메소드들과 사용할 수 없다는 점을 조심하시면 쉽게 푸실 수 있을 것 같습니다