[JS] 백준 24267번 - 알고리즘의 수행 시간 6

 

 

문제 24267번

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

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

 

이번 MenOfPassion 알고리즘은 for문이 3개(삼중)인데,

i는 1부터 n-2,

j는 i+1부터 n-1,

k는 j+1부터 n까지의 범위로 수행한다.

 

n이 7이라고 가정했을 때,

i는 1부터 5, j는 i+1부터 6, k는 j+1부터 7까지이다.

(i=1) (j = 2~6)

          (j=2)      (k= 3~7)

          (j=3)      (k= 4~7)

          (j=4)      (k= 5~7)

          (j=5)      (k= 6~7)

          (j=6)      (k= 7)           => 5+4+3+2+1 = 15

 

(i=2)(j= 3~6)

          (j=3)      (k= 4~7)        => 4+3+2+1 = 10

 

 

...

 

 

(i=5)(j= 6)

       (j=6)      (k= 7)        => 1

 

 

 

음... 뭔가 규칙을...

못 찾겠어서 다른 분 풀이를 참고했다.

1부터 n까지의 숫자 중에서 3가지(i,j,k에서 하나씩)를 뽑아 중복 없이 크기 순으로 작성하는 경우의 수가 수행 횟수라고 한다. (여기서 확률을 보니 반갑네...)

 

nCr = n!/((n-r)!*r!)

n은 최대 몇까지의 숫자인지, r은 뽑는 숫자의 개수이다.

만약 n이 7이면, 

 

그래서 시간 복잡도는 O(n*(n-1)*(n-2)/6)이고, 최고차항의 차수는 3이 된다.

 

[참고] https://velog.io/@gayeong39/%EB%B0%B1%EC%A4%80-24267-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%ED%96%89-%EC%8B%9C%EA%B0%846

 

 

 

 

 

const readFileSyncAdress = process.platform === 'linux' ? '/dev/stdin':'./input.txt'
const input = require("fs").readFileSync(readFileSyncAdress).toString().trim();

let n = (BigInt(input)*BigInt(input-1)*BigInt(input-2))/BigInt(6);

console.log(`${n}`)
console.log(3)

 

중간에 계속 타입에러가 나서 왜 그러나 했더니 BigInt를 내가 잘못쓴 것 같다.