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

문제

 

처음에 멘붕이 왔다.

3중 for문이니 시간복잡도는 O³ 되겠거니~ 하고 있는데 횟수를 못 구하겠다.

결국 해결 못하고 답을 찾았더니 포스팅은 꽤 나오는데 명확히 나를 이해시키지 못했다.

그러다가 덕킹라쿤님의 블로그를 발견 https://duckingracoon.tistory.com/3  여기에 식 유도를 해 두셨는데 

수학을 10년을 안 봐서 그런지 시그마 어떻게 풀어야 할지 모르겠다 ㅋㅋㅋㅋ 정말 많은 시간을 투자해서 해결했다 너무 기뻐서 포스팅을 남긴다...

풀이

일단 합공식을 알아두자 여기에 필요한 정도만 알아두고

i가 1부터 시작해 n-2까지

j가 i+1부터 시작해 n-1까지

k가 j+1부터 시작해 n까지 이 조건을 식으로 표현하면

다음과 같이 되고 첫 번째 시그마를 풀면

위의 k에 대한 식이 아닌 상수를 해결하는 방법을 이용해서 밑의 결과를 나타냅니다.

두 번째 시그마를 풀어보면 

합공식을 이용해서 미지수 j에 i+1을 넣어 이와 같은 결과를 낸 거죠.. 저는 도저히 이해가 안 가는 거예요 합공식은 알고 있지만 n을 껴두고? 이게  되는 건가? 이해를 해보려고 진짜 씨름을 하다가 결국은 해냅니다 ㅜㅜ

i+1부터 n-1까지 직접 대입을 하고 두 개를 합쳐보면 위와 같이 결과를 도출할 수 있게 됩니다. 

마지막 시그마도 정리해 보시죠

합공식을 사용해서 풀어내고 정리하면 다음과 같이 값을 얻을 수 있습니다!!

코드는

import java.util.Scanner;

public class No24267 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextInt();

        System.out.println((n*(n-1)*(n-2))/6);
        System.out.println(3);

    }
}

합공식의 정리를 처음부터 봤다면 단번에 이해를 했을 텐데.. 시간을 너무 많이 사용했습니다.. ㅎㅎ 

이참에 시그마를 공부하게 되어서 뭐 좋게 생각하기로 했습니다!

 

감사합니다!!