[BOJ] 32829 - Bottles

유빈·2025년 5월 28일

boj python

Algorithms

목록 보기

29/35

1. 문제 링크

BOJ 32829번 - Bottles

2. 걸린 시간

40분

3. 문제 풀이

input = open(0).readline

runner, interval = map(int, input().split())
times_by_runner = [[] for _ in range(runner)]
cnt_list = [[] for _ in range(interval)]

for j in range(runner):
    time_interval = list(map(int, input().split()))
    for t in range(interval):
        if t == 0:
            times_by_runner[j].append((0, time_interval[0]))
        else:
            times_by_runner[j].append((times_by_runner[j][t-1][1], times_by_runner[j][t-1][1] + time_interval[t]))

for i in range(interval):
    runner_in_interval = []  # 각 구간에서의 러너의 시간 튜플 저장
    for r in range(runner):
        runner_in_interval.append(times_by_runner[r][i])

    start, end = float('inf'), float('inf')
    cnt = 1
    runner_in_interval.sort(key = lambda x: x[1])

    end = runner_in_interval[0][1]

    for r in range(1, runner):
        if runner_in_interval[r][0] < end or (runner_in_interval[r][0] == runner_in_interval[r-1][0] and runner_in_interval[r][1] == runner_in_interval[r-1][1]):
            cnt += 1
        else:
            cnt_list[i].append(cnt)
            cnt = 1
    cnt_list[i].append(cnt)

for c in cnt_list:
    print(max(c), end=' ')

처음에는 위와 같이 풀었다.
주어진 테스트 케이스 3개는 잘 돌아갔지만, 막상 제출해보니 틀렸습니다가 떴다.

    for r in range(1, runner):
        if runner_in_interval[r][0] < end or (runner_in_interval[r][0] == runner_in_interval[r-1][0] and runner_in_interval[r][1] == runner_in_interval[r-1][1]):
            cnt += 1
        else:
            cnt_list[i].append(cnt)
            cnt = 1
    cnt_list[i].append(cnt)

이 로직은 단순히 해당 range(interval)에서의 runner의 start가 가장 start가 앞선 runner의 end보다 작은지만 확인하여 겹친다고 판단한다.

이 부분에서 문제가 있을거라고 바로 생각이 들었다.

위의 방법에서 놓친 부분은 다음과 같다.

두 runner가 다른 range에 속해 있어도 겹칠 수 있다.

최종 풀이

input = open(0).readline

runner, interval = map(int, input().split())
times_by_runner = [[] for _ in range(runner)]
cnt_list = [[] for _ in range(interval)]

for j in range(runner):
    time_interval = list(map(int, input().split()))
    for t in range(interval):
        if t == 0:
            times_by_runner[j].append((0, time_interval[0]))
        else:
            times_by_runner[j].append((times_by_runner[j][t-1][1], times_by_runner[j][t-1][1] + time_interval[t]))

for i in range(interval):
    runner_in_interval = []  # 각 구간에서의 러너의 시간 튜플 저장
    for r in range(runner):
        runner_in_interval.append(times_by_runner[r][i])

    events = []
    for start, end in runner_in_interval:
        events.append((start, 1))
        events.append((end, -1))

    events.sort()

    cnt = 0
    max_cnt = 0
    for _, c in events:
        cnt += c
        max_cnt = max(max_cnt, cnt)

    print(max_cnt, end=' ')