[백준] 2775: 부녀회장이 될테야 (javascript)

Link

2775번: 부녀회장이 될테야

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력 > 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
출력 > 각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.
제한 > 1 ≤ k, n ≤ 14

| 예제 입력

2
1
3
2
3

| 예제 출력

6
10

 

제출

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `2
    1
    3
    2
    3`
).split("\n");

const [T, ...data] = input;
const test_case = [];

for (let i = 0; i < data.length; i += 2) {
  test_case.push(data.map((num) => num.replace(/(\s*)/g, "")).slice(i, i + 2)); // slice() 메서드는 end 미포함이므로 i+2까지 지정
}

for (let i = 0; i < T; i++) {
  const k = Number(test_case[i][0]);
  const n = Number(test_case[i][1]);

  const resident = Array.from(Array(k + 1), () => new Array(n).fill(0));

  // 0층에 i호에는 i명이 산다.
  for (let i = 1; i <= n; i++) {
    resident[0][i] = i;
  }

  // k층 n호에는 (k-1층 n호) + (k층 n-1호)명이 산다.
  for (let i = 1; i <= k; i++) {
    for (let j = 1; j <= n; j++) {
      resident[i][j] = resident[i - 1][j] + resident[i][j - 1];
    }
  }

  console.log(resident[k][n]);
}

 

풀이과정

첫 번째 풀이 - 실패

테스트 케이스가 한 줄씩 입력되므로, slice를 통해 입력된 테스트 케이스를 두 개씩 묶어준다.

 

층수가 증가하면 거주민 수가 1씩 늘어나고, 호수가 증가하면 1부터 n까지의 합이 더해진다.

따라서, k가 층수, n이 호수라고 할 때,

                 n
(k - 1) +   ∑ n(n+1) / 2 가 k층 n호에 거주자 수이다.
               k=1

 

0층의 거주자 수는 호수가 증가함에 따라 1, 2, 3, ... 의 순으로 증가하기 때문에

1층의 거주자 수는 1~n까지의 덧셈이다.

 

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `2
      1
      3
      2
      3`
)
  .replace(/(\s*)/g, "")
  .split("");

const [T, ...data] = input;
const test_case = [];

for (let i = 0; i < data.length; i += 2) {
  test_case.push(data.slice(i, i + 2)); // slice() 메서드는 end 미포함이므로 i+2까지 지정
}

for (let j = 0; j < T; j++) {
  const k = Number(test_case[j][0]);
  const n = Number(test_case[j][1]);

  let sum = 0;

  if (k === 1) {
    sum = (n * (n + 1)) / 2;
  } else {
    for (let m = 2; m <= n; m++) {
      sum += (m * (m + 1)) / 2;
    }
  }

  console.log(k - 1 + sum);
}

🔼 0층의 거주자 수를 구했을 때 k-1 < 0 이 되므로 추가적인 예외 처리가 필요했고,

0층은 호수만큼 거주자가 있기 때문에 해당 조건에 맞는 처리도 해야한다.

그리고 간과했던 건 현재 input을 하나의 string으로 합치고, 2개씩 숫자를 나눠서 test_case로 저장하고 있기 때문에

k나 n이 10이 넘어가면 10이 그대로 들어가지 않고 1, 0 나눠지면서 원치 않은 모양의 test_case가 나오게 된다.

 

두 번째 제출 - 실패

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `2
    0
    1
    2
    3`
).split("\n");

const [T, ...data] = input;
const test_case = [];

for (let i = 0; i < data.length; i += 2) {
  test_case.push(data.map((num) => num.replace(/(\s*)/g, "")).slice(i, i + 2));
}

for (let j = 0; j < T; j++) {
  const k = Number(test_case[j][0]);
  const n = Number(test_case[j][1]);

  let sum = 0;
  let resident = 0;

  if (k === 0) {
    resident = n;
  } else if (k === 1) {
    resident = (n * (n + 1)) / 2;
  } else {
    for (let m = 2; m <= n; m++) {
      sum += (m * (m + 1)) / 2;
    }
    resident = k - 1 + sum;
  }

  console.log(n === 1 ? 1 : resident);
}

🔼 test_case에 넣을 data 더미 공백을 제거하고 slice를 했더니 k, n이 10이 넘어가도 test_case에 잘 들어가는 것을 확인할 수 있다.

그리고, k가 0일때, 1일때, 아닐 때를 나눠서

층수가 0일때는 거주자를 호수만큼, 층수가 1일때는 1+2+... n, 층수가 1보다 클 때는 (층수 - 1)에 거주자들의 합으로 했다.

여기서 호수가 1이라면 1이 출력되므로 console.log에 n이 1일 때의 조건을 걸어 출력했는데 오답이었다.

 

++) 생각해보니 저런식으로 sum을 구하고 resident에 넣게 되면 k층 2호 까지는 식이 성립하지만 그 이후부터는 식이 성립하지 않게 된다.

세 번째 제출 - 정답

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `2
    1
    3
    2
    3`
).split("\n");

const [T, ...data] = input;
const test_case = [];

for (let i = 0; i < data.length; i += 2) {
  test_case.push(data.map((num) => num.replace(/(\s*)/g, "")).slice(i, i + 2)); // slice() 메서드는 end 미포함이므로 i+2까지 지정
}

for (let i = 0; i < T; i++) {
  const k = Number(test_case[i][0]);
  const n = Number(test_case[i][1]);

  // resident[k+1][n] (0으로 초기화하여 생성)
  const resident = Array.from(Array(k + 1), () => new Array(n).fill(0));

  // 0층에 i호에는 i명이 산다.
  for (let i = 1; i <= n; i++) {
    resident[0][i] = i;
  }

  // k층 n호에는 (k-1층 n호) + (k층 n-1호)명이 산다.
  for (let i = 1; i <= k; i++) {
    for (let j = 1; j <= n; j++) {
      resident[i][j] = resident[i - 1][j] + resident[i][j - 1];
    }
  }

  console.log(resident[k][n]);
}

결국 다른 분의 풀이를 참고해서 문제를 해결했다.

2차 배열을 만들어서 재귀를 이용하여 문제를 풀면 해결할 수 있다.

k와 n을 구할 때 test_case의 요소로 넣어도 되지만, shift() 메서드를 사용해서 input에서 첫 번째 요소부터 하나씩 빼서 k, n에 할당해도 된다.

 

https://velog.io/@hadam/JS-%EB%B0%B1%EC%A4%80-2775-%EB%B6%80%EB%85%80%ED%9A%8C%EC%9E%A5%EC%9D%B4-%EB%90%A0%ED%85%8C%EC%95%BC

[JS] 백준 2775 부녀회장이 될테야

 

개념

Array.prototype.slice()

• 배열에서 괄호 안에 지정한 시작점부터 끝지점까지 복사하여 새로운 배열 객체를 반환한다.
• 원본 배열은 바뀌지 않는다.
• 매개변수
  
  • 첫 번째 인자 : begin
    • 잘라내기 할 시작점
    • begin이 undefined인 경우, 0번 인덱스부터 slice 된다.
    • begin이 배열의 길이보다 클 경우 빈 배열이 반환된다.
  • 두 번째 인자 : end
    • 잘라내기를 끝낼 종료지점
    • end 인덱스는 제외하고 추출된다.
    • ex) arr.slice(1,4) 의 경우, arr[1]~arr[3]까지 추출
    • end가 생략될 경우 배열의 끝까지 slice 된다.

Array.prototype.shift()

• 배열에서 첫 번째 요소를 제거하고, 제거된 요소를 반환한다.

---

Comment

머리를 꽁꽁 싸매다가 결국 다른 사람의 풀이를 참고해서 풀었다.

많이 고민해서 풀어내는 것도 좋지만, 새로운 아이디어를 얻는 것도 또 하나의 성장이라 생각한다!