[BOJ] 2979번 - 트럭주차

트럭주차

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

 

문제 정의

---

상근이는 트럭 3대를 가지고 있고 각 트럭의 주차요금을 계산해야 한다. 각 트럭이 주차장에 도착/떠난 시간이 입력으로 주어지는데,

이 때 ‘어떤시간’에 몇 대의 트럭이 주차되어 있느냐에 따라서 트럭 당 주차요금이 계산된다.

그렇기 때문에 1분에 트럭이 1대 주차되어있는지, 2대 주차되어 있는지에 따라 요금이 다르므로 각 트럭마다 주차 요금을 계산 후 합산하면 된다.

접근 방법

---

구현 문제이고 시간의 범위가 1~100 이라서 시간 초과는 생각하지 않았다.

처음 접근 방법은 다음과 같다.

1. 트럭의 도착/떠난 시간을 times 리스트에 넣고 가장 마지막에 나간 트럭의 시간을 last 변수에 저장한다.
2. 1~last 까지 각 시간마다 몇 대가 주차되어 있는지 확인 후 count 한다.
3. 각 트럭의 도착/떠난 시간을 확인하면서 count 변수에서 범위만큼 자른 후 각각 요금을 계산한다.

이렇게 했을 때 예제 2개의 답은 출력했지만 제출 했을 때 ‘실패’가 나왔다. 아직도 어디서 틀렸는지 파악을 못했다.

오래 고민할 문제는 아니라고 생각했고 다른 사람의 풀이를 보니 훨씬 더 쉽게 접근할 수 있는 방법이 있었다.

두번째 접근

1. 시간의 범위가 1~100으로 작기 때문에 불필요한 변수를 만들지 않을 수 있다.
2. 입력받은 트럭의 도착/떠난 시간을 기준으로, 1~100까지 times 변수에 몇 대의 트럭이 주차되어 있는지 세준다.
3. times 에서 트럭이 주차된 수만큼 고려해 요금을 계산해준다.

 

문제 해설

---

• 길이가 101인 times 리스트를 만든다.
• 트럭 3대의 도착/떠난 시간을 for문을 돌면서 times 에 해당하는 인덱스에 값을 +1 해준다. → 그 시간에 트럭이 있음을 카운트 해주는 것이다.
• 다시 times 리스트를 확인하면서 주차된 트럭수가 몇 대인지에 따라 요금을 계산해준다.
  • 0대면 pass
  • 1대면 A원
  • 2대면 (2대 * B) 원
  • 3대면(3대 * C) 원

 

풀이

---

1. 정답 풀이
# 각 트럭의 주차요금을 계산해야 한다.
# 1분에 몇대 주차되어 있는지에 따라 요금이 달라진다.
# 시간 범위: 1~100

A, B, C = map(int, input().split())
times = [0]*101

for _ in range(3):
    start, end = map(int, input().split())
    for i in range(start, end):
        times[i] += 1

result = 0        
# 주차 요금 계산하기        
for t in times:
    if t == 0:
        pass
    elif t == 1:
        result += A
    elif t == 2:
        result += (B)*2
    else:
        result += (C)*3

print(result)

2. 첫번째 접근 풀이 (실패한 풀이)
# 상근이는 총 3대의 트럭 가지고 있음.
# 현재 주차 수를 담는 파킹리스트가 필요

A, B, C = map(int, input().split()) # 1분에 한 대 당 몇원?
times=  []  # 트럭의 출발/도착 시간 정보 리스트

for _ in range(3):
    start, end = map(int, input().split())  # 트럭의 도착시간, 떠난시간
    last = max(1e-9, end)   # 가장 마지막에 나간 트럭의 떠난 시간
    times.append((start, end))

count = []  # 시간마다 몇 대가 있었는지 

for i in range(1, last+1):
    cnt = 0
    for t in times:
        if i >= t[0] and i < t[1]:
            cnt += 1    # 트럭이 주차되어 있으면 주차된 트럭 수 +1
    count.append(cnt)   # i 시간에 주차되어 있는 총 트럭 수 기록(count[0]은 시간 1~2 에 주차된 트럭 수)
# count = [1, 2, 3, 3, 2, 1, 1, 0]

# 각 트럭의 주차 요금 계산
result = 0
for t in times: # 각 트럭의 출/도착 시간을 확인하면서,
    tmp = count[t[0]-1:t[1]-1]  # (출발시간-1, 도착시간-1) 만큼 슬라이싱 한 뒤에
    for tm in tmp:  # 몇 대 주차되어 있는지 따라서 요금을 계산한다.
        if tm == 1:
            result += A # 1분에 1대일 때
        elif tm == 2:
            result += B # 1분에 2대일 때
        else:
            result += C # 1분에 3대일 때
print(result)

 

정리

---

문제는 쉽다고 생각했으나 바로 코드 구현이 되지 않았다. 아직 구현 문제는 실력이 부족함을 알게 된 문제였다.

시간 복잡도는 $O(N^2)$ 이고 시간의 범위가 1~100 이므로 여유로운 편이기게 크게 신경쓰지 않았다.