[백준] 24267번 : 알고리즘 수업 - 알고리즘의 수행 시간 6 (브론즈 Ⅱ) - Java/자바

---

✅ 문제

문제링크

🔗 https://www.acmicpc.net/problem/24267

 

---

✅ 풀이

🔹 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long n = Long.parseLong(br.readLine());
        StringBuilder sb = new StringBuilder();
        sb.append(n * (n - 1) * (n - 2) / 6).append("\n").append(3);
        System.out.println(sb);
    }
}

 

문제의 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;
}

여기서 i = 1 ~ n - 2까지, j = i + 1 ~ n - 1까지, k = j + 1 ~ n까지 이다.

이를 예를 들어보면 다음과 같다.

n = 7일 경우,

 

i = 1이면,

• j = 2일때, k = 3, 4, 5, 6, 7
• j = 3일때, k = 4, 5, 6, 7
• j = 4일때, k = 5, 6, 7
• j = 5일때, k = 6, 7
• j = 6일때, k = 7

i = 2이면,

• j = 3일때, k = 4, 5, 6, 7
• j = 4일때, k = 5, 6, 7
• j = 5일때, k = 6, 7
• j = 6일때, k = 7

 

i = 3이면,

• j = 4일때, k = 5, 6, 7
• j = 5일때, k = 6, 7
• j = 6일때, k = 7

 

i = 4이면,

• j = 5일때, k = 6, 7
• j = 6일때, k = 7

 

i = 5이면,

• j = 6일때, k = 7

위에 나열한 예시를 잘보면 고등수학에서 배운 조합의 예시와 매우 비슷하다.

i, j, k가 모두 같은 값이 없고 다른 값을 가진다는 것을 알 수 있다.

따라서 n = 7이면, 7개 숫자 중에서 i, j, k 즉, 중복 없이 3개 숫자를 선택하는 경우인 것이다.

조합 공식은 다음과 같다.

문제에서 입력의 크기 n이 1 ≤ n ≤ 500,000 이므로 세제곱하면 int 타입의 범위를 넘어가므로 Long 타입으로 선언하고 받아준다.

첫째줄에 n * (n - 1) * (n - 2) / 6 의 결과값을 출력하고, 최고차항의 차수는 항상 3이므로 3을 출력해준다.

 

🔹 결과

 

🔹 알게된 정보

• 코드 수행 횟수에서 조합의 개념을 찾았고 이를 통해 횟수 계산을 해보았다.

 

---