문제

찬우는 친구들과 고양이 카페에 가려 한다.

고양이 카페에는 N마리의 고양이가 있다.
i번째 고양이의 무게는 w_i이다. 찬우와 친구들은 모두 고양이를 사랑하기 때문에 무릎 위에 고양이를 정확히 2마리 데리고 있으면 행복해진다. 하지만 허약한 찬우와 친구들은 데리고 있는 두 고양이의 무게의 합이 K를 넘는다면 버티지 못할 것이다.

각 고양이의 무게와 한 명이 버틸 수 있는 최대 무게 K가 주어질 때 최대 몇 명이 행복해질 수 있는지 구해보자.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. (1 <= N <= 5,000) / (1 <= K <= 10^9)

둘째 줄에는 각 고양이의 무게를 의미하는 N개의 정수 w_1, w_2, ..., w_N이 공백으로 구분되어 주어진다. (1 <= w_i <= K)

출력

행복해질 수 있는 사람의 수의 최댓값을 출력한다.

예제 입력

5 20
8 16 11 2 4

예제 출력

2

내가 했던 풀이 방법

1. 고양이의 무게를 내림차순으로 정렬한다. (최댓값을 구하기 위해 무거운 고양이 먼저 해결해주어야 한다. 무거운 고양이가 다른 고양이와 무게를 합쳐도 K가 되지 않도록 해주어야 한다. 이 경우를 최대로 해야하므로, 다른 고양이는 남은 고양이 중에서 합쳤을 때 K가 되지 않으면서, 가장 무거운 고양이로 해주면 된다.)
2. count를 0으로 초기화한 뒤, 다음의 내용을 0부터 N-2번 반복한다. (N-2까지 하는 이유는 3번에서 사용할 start와 end는 고양이의 무게를 나타낸다. (정확하게는 해당하는 고양이 무게의 index) start는 항상 end보다 작다고 가정해놓고 풀기 때문에 N-1번째 index의 고양이는 start가 될 수 없다.)
3. start를 i로 end를 start+i로 저장한 뒤, end가 N이 될 때까지 while문을 수행한다.
4. start가 가리키는 무게의 값이 K보다 작고, start와 end의 무게의 합이 K이하일 경우, start와 end에 위치한 값을 K+1로 바꿔주고, count를 증가시켜주고, while문을 탈출한다.(start가 가리키는 무게가 K와 같을 경우를 무시해주는 이유는 2마리를 데리고 있어야 하기 때문에 절대 무게의 합이 K가 될 수 없기 때문이다.) (K+1로 바꿔주는 이유는 K보다 작은 값을 무시하고 있기 때문에 K+1로 바꿔줌으로써 이미 데리고 있는 고양이를 무시하고 계산할 수 있다. K+1은 K이상이라면 무슨 수라도 괜찮다. K+1의 개수/2를 통해 최댓값을 구할 수 있으나, count를 통해 최댓값을 구한다.)
5. while문을 탈출하지 못한 경우, end를 1 증가시킨다.
6. count를 출력한다.

코드

const fs = require('fs');
let [n, input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(n.trim().split(' ')[0]);
let K = Number(n.trim().split(' ')[1]);
let weights = input.trim().split(' ').map(Number);
weights.sort((a, b) => b - a);

let start = 0;
let end = 0;
let count = 0;
for (let i = 0; i < N - 1; i++) {
  start = i;
  end = start + 1;
  while (true) {
    if (end === weights.length) break;
    if (weights[start] < K) {
      if (weights[start] + weights[end] <= K) {
        weights[start] = K + 1;
        weights[end] = K + 1;
        count++;
        break;
      }
    }
    end++;
  }
}

console.log(count);

회고

실제 제출에서는 break를 빼먹었음에도 성공했다. 생각보다 컷이 빡세지는 않은 것 같다. 물론 K+1로 바꿔주면서 if문에 해당하는 경우가 나오지 않았지만.. 그래도 쓸데없이 end값을 계속 증가시켜주었을텐데.. 당연한 것들이라 놓치는 것들이 많다. 그래놓고 틀렸으면 멘탈이 나갔을테지... 문제를 풀 때 실수를 빨리 줄여야 하는데...