백준 24267번 풀이 (Java)

 

문제는 다음과 같다.

수행 횟수와 시간 복잡도를 구하는 문제이다.

우선 직관적으로 반복문이 3개가 중첩되어 있으므로 O(n^3)의 복잡도를 가질것으로 보인다.

그냥 반복문에다가 count를 넣으면 간단히 해결될 문제이지만 그러면 문제를 푸는 의미가 없다.

따라서 다른 풀이가 필요하다.

 

 

 

[풀이 1]

삼중 for문을 분석해보면

첫번째 for문은 1부터 n-2

두번째 for문은 i+1부터 n-1

세번째 for문은 j+1부터 n 까지 반복된다.

 

 

먼저 1부터 10까지 반복하는 for문 하나의 수행 횟수를 시그마로 나타내보면

다음과 같다. (윗끝 - 아랫끝 + 1) = (10 - 1 + 1) = 10 이다.

 

 

 

따라서 위의 삼중 for문을 시그마 공식으로 나타내면

 

 

그리고 순차적으로 시그마 공식을 계산해보면

 

 

 

⬇️

 

 

 

⬇️

이렇게 정리된 수식을 얻게된다.

유도 과정을 안적어서 그렇지 솔직히 좀 노가다이다.

풀기위해선 등차수열의 합공식과 1차식 2차식 시그마 공식을 써야했다.

 

 

 

[풀이2]

그렇다면 다른 방법은 없을까?

먼저 n = 7이라고 하고

(i,j,k)에 수를 넣어보면서 규칙을 찾아보자

 

(1,2,3) ..... (1, 2, 7)

(2,3,4).....(2,3,7)

...(5,6,7)

어랏 이건 조합인데????

 

그렇다 그동안 잊고 살았던 조합공식! n개에서 중복되지 않은 3개를 뽑는 경우의수

즉 nC3 

 

이 나오게 된다.

 

풀이2번처럼 생각 못한 이유가 아마 대부분

수행횟수 그 자체에 집중해서 분석했기 때문이라고 본다.

i, j, k에 각각 들어가는 값들을 집중해서 살펴보면 3개를 뽑는 조합인 것을 금방 알아챌 수 있었을 것이라고 생각한다.

 

따라서 코드를 작성해보면

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        System.out.println((a*(a-1)*(a-2))/6);
        System.out.println(3);
    }
}

 

(참고로 사소하지만 자료형에 조심하자 int써서 한번 틀렸었다)