[BOJ] 24267번 - 알고리즘 수업 (알고리즘의 수행 시간6)

사용언어 : javascript - node.js

 

#문제

출처 : 백준 온라인

 

#접근방법

문제에서 준 MenOfPassion 알고리즘을 보고, 요구하는 출력 조건을 확인해보자.

 

1)첫 번째 줄: 코드1의 수행 횟수 출력 

  >> for 반복문이 세 번 중첩된 걸 코드에서 확인할 수 있다. 입력한 값을 n이라고 했을때,

      중첩된 반복문 중 첫 번째 반복문은 n-2번 수행하고,

      두 번째 반복문은 첫 번째 반복문의 (index 값+1) - (n-1) 만큼 실행,

      세 번째 반복문은 두 번째 반복문 (index 값+1) - n 만큼 실행한다.

  ex) n의 입력이 7이라고 가정한 예시

    - i 가 1일 경우, j는 5번 실행(2 ~ 6),

       - j가 2일 경우,  k는 5번 실행(3 ~ 7) 

       - j가 3일 경우,  k는 4번 실행(4 ~ 7) 

       - j가 4일 경우,  k는 3번 실행(5 ~ 7) 

       - j가 5일 경우,  k는 2번 실행(6 ~ 7) 

       - j가 6일 경우,  k는 0번 번실행

    - i 가 2일 경우, j는 4번 실행(3 ~ 6),

       - j가 3일 경우,  k는 4번 실행(4 ~ 7) 

       - j가 4일 경우,  k는 3번 실행(5 ~ 7) 

       - j가 5일 경우,  k는 2번 실행(6 ~ 7) 

       - j가 6일 경우,  k는 0번 실행

     ...

    

  >> 열심히 써보면서 생각해 보다가.. 시간이 너무 소요돼서 다른 분들의 풀이를 찾아보다가 제일 이해가 가는 분의 풀이를 참고해 풀었다.

        첫 번째 반복문은 1부터 n-2까지 반복

        두 번째 반복문은 i+1부터 n-1까지 반복

        세 번째 반복문은 j+1부터 n까지 반복...

          =>> 시그마 합의 공식을 이용해 전체 횟수를 구하면 "(n-2)*(n-1)*n/6"  공식을 도출해 낼 수 있다.

출처 : https://rightbellboy.tistory.com/206

 

 

2)두 번째 줄: 코드의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. (단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

   >> 위에서 도출한 공식의 최고 차항은 3이므로 두 번째줄은 3으로 출력 되어야 한다.

     + 여기서 시간 복잡도는 O(n^3) 이 된다.

 

#제출코드

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

const result = (BigInt(num - 2) * BigInt(num - 1) * BigInt(num)) / BigInt(6);

console.log(`${result}`);
console.log(3);