기타줄

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

 

나의 풀이

import sys

def _gitar(N, M):
    s_min_pr, n_min_pr = float('inf'), float('inf')
    for _ in range(M):
        s_pr, n_pr = map(int, sys.stdin.readline().rstrip().split())
        s_min_pr, n_min_pr = min(s_min_pr, s_pr), min(n_min_pr, n_pr)

    N_mod, N_namozi = (N // 6), (N % 6)
    if (N_mod == 0):
        if (s_min_pr <= (n_min_pr * N)):
            return s_min_pr
        else:
            return (n_min_pr * N)
    else:
        if (s_min_pr < (n_min_pr * 6)):
            now_pr = s_min_pr * N_mod # 일단 세트권 구매
            if (s_min_pr <= (n_min_pr * N_namozi)): # 남아있는 것 보다 세트가 더싸면 걍 세트 구매
                return now_pr + s_min_pr
            else:
                return now_pr + (n_min_pr * N_namozi)
        else:
            return (n_min_pr * N)

N, M = map(int, sys.stdin.readline().rstrip().split())
print(_gitar(N, M))

 

시간 복잡도

for _ in range(M) : 기타줄 브랜드를 순회하며 최소 가격을 최신화 ( 선형 시간 복잡도 )
이후 계산 로직은 상수 시간
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )