Homile

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

122333444455555

11060446

문제풀이(1)

처음엔 간단하게 Math.sqrt를 사용해서 제곱근을 구하면 될 것이라 생각해서 풀어보았다.

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

// 제곱근을 찾는다.
let result = Math.floor(Math.sqrt(n));

// 제곱근보다 작을 경우 +1을 해준다.
console.log(result ** 2 < n ? result + 1 : result);

문제풀이(2)

이진 탐색으로 푸는 방법이 있다고하여 구현해보았다.

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

const binarySearch = (num) => {
  let low = 0;
  let high = num;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (mid * mid < num) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return low;
};

console.log(binarySearch(n));

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

2

1

10

3

문제풀이(1)

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
위의 공식을 실행하면 된다. 횟수를 카운트해서 출력한다.
하지만, 10^6승의 수가 나왔을 경우 연산횟수가 많아 질 수 있기 때문에 dp로 이전 값을 가져와서 계산하는 방법을 사용했다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let num = Number(require("fs").readFileSync(filePath).toString().trim());

const dp = new Array(num + 1).fill(0);

for (let i = 2; i <= num; i++) {
  dp[i] = dp[i - 1] + 1;

  if (i % 2 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 2] + 1);
  }

  if (i % 3 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  }
}

console.log(dp[num]);

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

5 4
2
8
10
7

7 21

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

const [N, M] = input.shift().split(" ").map(Number);
const arr = input.map(Number);
arr.sort((a, b) => b - a);

const answer = [];

for (let i = 0; i < arr.length; i++) {
  if (i + 1 > N) {
    break;
  }

  // total - 최대 수익, value - 달걀 가격
  answer.push({ total: (i + 1) * arr[i], value: arr[i] });
}

answer.sort((a, b) => b.total - a.total);

console.log(answer[0].value, answer[0].total);

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

3
2 1
8 3
5 7

15

1 2(1번소) 3(1번소 검사완료) 4 5(3번소) 6 7 8 9 10 11 12(3번소 검사완료) 13(2번소) 14 15(2번소 검사완료)
위와 같이 진행될 때 소는 먼저온 순서로 들어가는 형식이다. 그렇기때문에 소의 도착시간 순서로 정렬한 뒤 계산한다.
배열 순회할 때 마다 time에 start + end를 더해준다.
이때, 현재 time > start이면 time에 end 만 더해주고, time <= start 일 경우 start - time + end로 계산한다.
start - time을 하는 이유는 이전에 지나간 시간은 start에서 제거를 해야하기 때문이다.

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

const arr = input.map((el) => el.split(" ").map(Number));
arr.sort((a, b) => a[0] - b[0]);

let time = 0;

arr.forEach((value) => {
  const [start, end] = value;
  if (time > start) {
    time += end;
  } else {
    time += start - time + end;
  }
});

console.log(time);

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

10

19

15624번 피보나치 수 7과 같은 DP 문제이다. 조건은 조금 다르다.
f(n) = f(n-1) + f(n-3) 해당 조건에 맞게 로직을 구현하면 된다.
f(1) = f(2) = f(3) = 1
또한, Int 범위를 벗어나는 경우가 있기 때문에 Bigint를 사용해야한다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const N = Number(require("fs").readFileSync(filePath).toString().trim());

const dp = [BigInt(1), BigInt(1), BigInt(1)];

for (let i = 3; i < N; i++) {
  dp.push(dp[i - 1] + dp[i - 3]);
}

console.log(dp.at(-1).toString());

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

10

55

1000

517691607

문제풀이(1)

이전에 풀었던 1755번 숫자 놀이와 같은 DP 문제이다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const num = Number(require("fs").readFileSync(filePath).toString().trim());

const dp = [0, 1];

for (let i = 2; i <= num; i++) {
  dp.push((dp[i - 2] + dp[i - 1]) % 1000000007);
}

if (num === 0 || num === 1) {
  console.log(dp[num]);
} else {
  console.log(dp.at(-1));
}