์ˆ˜์„ ํ™”

[C++][๋ฐฑ์ค€|BOJ][์‹œ๊ฐ„๋ณต์žก๋„] 24267๋ฒˆ - ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…(์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„ 6) ๋ณธ๋ฌธ

๐Ÿฅ‚ C (++)

[C++][๋ฐฑ์ค€|BOJ][์‹œ๊ฐ„๋ณต์žก๋„] 24267๋ฒˆ - ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…(์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„ 6)

re.aom 2024. 2. 7. 01:51

๋ฌธ์ œ

์˜ค๋Š˜๋„ ์„œ์ค€์ด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰์‹œ๊ฐ„ ์ˆ˜์—… ์กฐ๊ต๋ฅผ ํ•˜๊ณ  ์žˆ๋‹ค. ์•„๋น ๊ฐ€ ์ˆ˜์—…ํ•œ ๋‚ด์šฉ์„ ํ•™์ƒ๋“ค์ด ์ž˜ ์ดํ•ดํ–ˆ๋Š”์ง€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด์„œ ํ™•์ธํ•ด๋ณด์ž.

์ž…๋ ฅ์˜ ํฌ๊ธฐ n์ด ์ฃผ์–ด์ง€๋ฉด MenOfPassion ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์„ ์˜ˆ์ œ ์ถœ๋ ฅ๊ณผ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ์ถœ๋ ฅํ•ด๋ณด์ž.

MenOfPassion ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

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;
}

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ž…๋ ฅ์˜ ํฌ๊ธฐ n(1 โ‰ค n โ‰ค 500,000)์ด ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ฝ”๋“œ1 ์˜ ์ˆ˜ํ–‰ ํšŸ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๋‘˜์งธ ์ค„์— ์ฝ”๋“œ1์˜ ์ˆ˜ํ–‰ ํšŸ์ˆ˜๋ฅผ ๋‹คํ•ญ์‹์œผ๋กœ ๋‚˜ํƒ€๋‚ด์—ˆ์„ ๋•Œ, ์ตœ๊ณ ์ฐจํ•ญ์˜ ์ฐจ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋‹จ, ๋‹คํ•ญ์‹์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์—†๊ฑฐ๋‚˜ ์ตœ๊ณ ์ฐจํ•ญ์˜ ์ฐจ์ˆ˜๊ฐ€ 3๋ณด๋‹ค ํฌ๋ฉด 4๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

7

์˜ˆ์ œ ์ถœ๋ ฅ 1

35
3

์ฝ”๋“œ1 ์ด 35ํšŒ ์ˆ˜ํ–‰๋˜๊ณ  ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์ด n3์— ๋น„๋ก€ํ•œ๋‹ค.

 

์ฝ”๋“œ1 ์ด 35ํšŒ ์ˆ˜ํ–‰๋˜๊ณ  ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์ด n3์— ๋น„๋ก€ํ•œ๋‹ค.

 


 

์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n^3) 3์ฐจํ˜•์ด๋‹ค.

โ€‹

 

 

 

#include <iostream>

int main() {
    long long n;
    std::cin >> n;
    std::cout << n * (n-1) * (n-2) / 6 << std::endl << 3;
}

 

 

 

 

 

Comments