문제 24267번
https://www.acmicpc.net/problem/24267
이번 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를 내가 잘못쓴 것 같다.
'백준 > JavaScript' 카테고리의 다른 글
[JS] 백준 2231번 - 분해합 (0) | 2024.03.17 |
---|---|
[JS] 백준 2798번 - 블랙잭 (1) | 2024.03.17 |
[JS] 백준 24266번 - 알고리즘의 수행 시간 5 (0) | 2024.03.14 |
[JS] 백준 24265번 - 알고리즘의 수행 시간 4 (0) | 2024.03.13 |
[JS] 백준 - 알고리즘 수행 시간 3 (0) | 2024.03.12 |