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

백준 24266번과 이어지는 문제이다.

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이 7이라고 가정하자.

i => 1 to (n - 2), 1 2 3 4 5

 

j => (i + 1) to (n - 1)

  => [i=1] 2, 3, 4, 5, 6

  => [i=2]     3, 4, 5, 6

  => [i=3]         4, 5, 6

  => [i=4]             5, 6

  => [i=5]                 6

 

k => (j+1) to n

  => [j=2] 3, 4, 5, 6, 7

  => [j=3]     4, 5, 6, 7

  => [j=4]         5, 6, 7

  => [j=5]             6, 7

  => [j=6]                 7

 

i에서 1 > j에서 2 > k에서 3~7 중 1개가 실행된다.

i에서 1 > j에서 3 > k에서 4~7 중 1개가 실행된다.

...

i에서 1 > j에서 6 > k에서 7~7 중 1개ㅏ 실행된다.

---

i에서 2 > j에서 3 > k에서 4~7 중 1개가 실행된다.

i에서 2 > j에서 4 > k에서 5~7 중 1개가 실행된다.

...

i에서 2 > j에서 6 > k에서 7~7 중 1개가 실행된다.

 

뭔가 느낌이 오지 않는가?

 

i, j, k에서 숫자를 하나씩 고르는데, 중복되는 경우가 없다.

 

이때 우리는 조합을 생각해볼 수 있다.

n중에서 r개를 뽑는 조합 말이다.

조합의 공식을 이용하여 nCr을 계산해보면, 

팩토리얼이 n*(n-1)*(n-2)*(n-3)! 으로 변환되어 분모와 약분되는 것에 유의하여 계산하면 됩니다.

 

처음에 문제를 봤을 때 잘 이해가 되지 않았는데, 직접 i, j, k를 구해보면서 조합이라는 것을 깨닫고, 조합 공식에 대입만 잘 하면 해답을 얻어낼 수 있었습니다.