백준 24263번 풀이

문제

https://www.acmicpc.net/problem/24263

24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2

단일 반복문의 실행 시간 출력하기.

 

Reference

https://nulls.co.kr/codeit/341

22. 주요 시간 복잡도 총정리

풀이

예제에 있는 코드를 파이썬으로 바꾸면

import sys

k = int(sys.stdin.readline())

def MenOfPassion(n):
    sum = 0
    for i in range(1, n+1):
        sum += i
    return sum

print(MenOfPassion(k))

대충 이렇게 된다. 0부터 시작하는 사람도 있었는데 예제 코드가

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

1 to n이라서 걍 1부터 했음.

 

import sys

k = int(sys.stdin.readline())

print(k)
print(1)

이게 정답이다. 왜죠? 쟤도 검색엔진이랑 동급임? 그런 게 아니고, 반복문은 입력 횟수에 따라 횟수가 선형적으로 증가하기 때문에 선형이다. 즉, 얘는 1차식이라 1. 뭔 소린지 모르겠다고? 저 위에 코드에 5를 쓰면 1+2+3+4+5가 되지만, 100을 쓰면 1+2+...+99+100이 되잖음.