[백준] 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 | C++ 풀이

# 문제

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

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

 

 

---

 

# 풀이

시간복잡도를 고려하는 단계에 이르렀다!

문제에서 제시한 MenOfPassion 알고리즘을 먼저 살펴보면 아래와 같다.

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; // 코드1
}

배열과 n이 주어지는데 이를 통해 i를 구한 후 배열 A의 i번째 원소를 반환하면된다.

입력에 제시된 n의 범위를 참고하면 어떤 n을 넣더라도 코드는 1회 수행, 수행시간은 상수 시간임을 알 수 있다.

따라서 시간 복잡도는 O(1)이고, 항상 1과 0을 개행하여 출력해주면 끝!

 

 

 

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    cout << 1 << '\n' << 0;
    return 0;
}

코드는 아주 간단하게 짤 수 있다.

 

 

 

 

 

---

 

 

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1