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

사용언어 : javascript - node.js

 

#문제

출처 : 백준 온라인

 

#접근방법

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

 

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

  >> for 반복문이 두 번 중첩된 걸 코드에서 확인할 수 있다. 입력한 값을 n이라고 했을때, 중첩된 반복문 중 첫 번째 반복문은 n-1번 수행하고, 두 번째 반복문은 첫번째 반복문의 (index 값+1) - n 만큼 실행한다.

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

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

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

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

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

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

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

  >> 예시를 보았을때, 실행 횟수는 1부터 n-1까지 공차가 1인 등차수열로 이루어진 것들의 합과 동일한 것을 알 수 있다.

      등차수열의 합 공식 중 첫번째 항과 마지막 항을 알 때의 공식 "n(첫번째항 + 마지막항)/2"을 사용하면 실행 횟수를 알 수 있다.

      따라서 첫번째 출력은 공식을 사용한 값이 출력되면 된다.

 

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

   >> 위에서 사용한 코드의 수행 횟수를 풀어쓰면 "첫번째 항 : 1, 마지막 항: n-1"이 되므로 최종적인 다항식은 "n(n-1)/2)"가 된다. 따라서 최고 차항은 2로 출력 되어야 한다.

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

 

#제출코드

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

console.log(Math.floor((num * (num - 1)) / 2));
console.log(2);