성준이와 초콜릿 ( 1674 번 )

1674번: 성준이와 초콜릿

 

---

🧠 알고리즘

• 브루트포스 (Brute Force, 완전 탐색)

 

✔️ 동작 방식

• 입력을 읽어와 Query, Chocolate, Coffee 정보를 각각 리스트에 저장
• 각 데이터 시간 순으로 정
• 각 Query 시각 순회하며 안전거리 계산
• 최종 안전거리가 1 미만이면 1.0, 그렇지 않으면 소수 첫째 자리까지 출력

---

 

🧾 코드

import sys

def _cr(time, ch, co):
    answer = 0
    for ch_time, ch_n in ch:
        if time >= ch_time:
            score = 8 * ch_n - ((time - ch_time)/12)
            if score > 0:
                answer += score
        else:
            break

    for co_time, co_n in co:
        if time >= co_time:
            score = 2 * co_n - ((time - co_time) * (time - co_time) / 79)
            if score > 0:
                answer += score
        else:
            break
    
    if answer > 1:
        return str(round(answer, 1))
    else:
        return '1.0'


def _main(lines):
    qy, ch, co = [], [], []
    for line in lines:
        line = line.rstrip().split()
        if line[0] == 'Query':
            qy.append(int(line[1]))
        elif line[0] == 'Chocolate':
            ch.append((int(line[1]), float(line[2])))
        elif line[0] == 'Coffee':
            co.append((int(line[1]), float(line[2])))

    qy.sort()
    ch = sorted(ch, key=lambda x:x[0])
    co = sorted(co, key=lambda x:x[0])

    for time in qy:
        print(f"{str(time)} {_cr(time, ch, co)}")

        
# 입력 다 받기
lines = sys.stdin.readlines()
_main(lines)

---

 

⏱️ 시간 복잡도

for time in qy : 시간을 순회하며 안전거리 출력 ( 선형 시간 복잡도 )
	print(f"{str(time)} {_cr(time, ch, co)}") : _cr 함수 ( 선형 시간 복잡도 )
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )