[백준] 24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6 (Node.js)

 

 

 

접근방식

우선 문제의 코드를 변경하면 아래와 같습니다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

--------------------------------------------------------------------

for (let i = 0; i < n - 2; i++) {
    for (let j = i + 1; j < n - 1; j++) {
      for (let k = j + 1; k < n; k++) {
      
      }
    }
  }

 

 

3중 for문을 통한 계산의 수행 횟수를 구해야하는데, 변수가 i, j, k가 있습니다.

이 과정에서 i < j < k 가 성립을 해야하는 상태이면서

i가 고정이 되면, j는 그다음 값, k는 j의 그 다음 값을 고르는 방식입니다.

 

i는 0부터 n - 2 까지 돕니다.

즉, n - 1번 반복합니다.(0부터 n-2까지니까 n-2+1)

 

j는 i + 1부터 n - 1까지 반복합니다.

i = 0이면, j는 1부터 n - 1까지 값을 가지며 n - 1번 반복합니다.

그리고 i가 증가할수록, j는 증가한 만큼 반복이 줄어듭니다.

 

k는 j + 1부터 시작해서 n까지 반복합니다.

i = 0이면 j = 1이고, k는 2부터 n까지 반복합니다.

즉, n - 2번 반복합니다.

j와 마찬가지로 i가 커지면, j가 커지면서 k가 반복하는 횟수도 줄어들게 됩니다.

 

종합적으로 따지면

i가 선택할 수 있는 경우는 n가지입니다. => i는 처음 선택할 수 있는 수가 아무거나 선택이 가능해서 n가지

j가 선택할 수 있는 경우는 n - 1가지입니다. => j는 i보다 큰 값만 선택할 수 있으므로 n-1가지

k가 선택할 수 있는 경우는 n - 2가지 입니다. => k는 i, j보다 큰 값만 선택할 수 있으므로 n-2가지

 

이를 조합으로 나타내면 

 

 

 

 

풀이 ⏰

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  // for (let i = 0; i < n - 2; i++) {
  //   for (let j = i + 1; j < n - 1; j++) {
  //     for (let k = j + 1; k < n; k++) {}
  //   }
  // }
  let n = BigInt(input[0]);
  n = (n * (n - 1n) * (n - 2n)) / 6n;
  console.log(n.toString());
  console.log(3);
});

 

백준 24267번 링크

👉 https://www.acmicpc.net/problem/24267