[Rust로 백준 하루 하나] 11-4. 알고리즘 수업 - 알고리즘의 수행 시간 4

문제 (24265번)

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

---

풀이

코드

use std::io;

fn main() {
    let mut n = String::new();
    io::stdin().read_line(&mut n).unwrap();
    let n = n.trim().parse::<f64>().unwrap();
    
    // O(n) = (n^2 - n) / 2
    println!("{}", (n*n - n) / 2 as f64);
    println!("2");
}

해설

안쪽 바깥쪽이 정확하게 곱으로 표현되는 것은 바깥 루프 1회당 안쪽 루프의 실행 횟수가 고정인 경우에만 해당되는 것이고, 이 코드에서는 둘이 독립적이지 않고 바깥 루프의 변수 값에 안쪽 루프의 실행 횟수가 영향을 받기 때문에 이를 종합적으로 고려하여 식으로 다 정리한 결과가 n * (n - 1) / 2인 것입니다. 종합적으로 고려한 것이 단순 곱으로 표현이 되느냐, 다른 식으로 계산해서 풀어써야 하느냐의 차이일 뿐, 후자라고 해서 여기에 뭘 또 곱해야 하는 건 아닙니다.

---

추가 학습

• 특이사항 없음