[백준] 시험감독 13458(구현)

hackyu 2019. 10. 19. 00:35

처음에 cnts라는 list에 N의 크기만큼 2차원배열을 만들어 각 인덱스를 1로 초기화하고 각 인덱스의 값에 더하고 마지막 sum을 통해 구현하였더니 시간초과가 났다.

처음 문제를 풀기 위해 설계 단계에서 cnts = N 이것과 두번째로는 위에 방식을 통한 것을 생각하고 2번째방식으로 구현했었다. 이후 처음에 생각한 것 처럼 하였더니 가볍게 문제가 풀렸다.

아마도 리스트를 생성하는 시간(입력 N)만큼 더 수행하고 해당 i가 A리스트에 어느 인덱스인지 서치하고, sum으로 각 계산하는 연산이 추가적으로 들어 시간초과가 된 것으로 생각한다.

굳이 리스트를 쓸 필요 없다면 리스트 만들지 말자. 그리고 시간초과가 났다면 불필요한 작업을 했던것에 대해 대비책을 생각하고 디버깅해야 할 것 같다.

단순하게 최소 N만큼의 주 감독관이 있고, 주감독관이 수용할 수 있는 인원이 벗어날 때 얼마만큼의 부 감독관을 사용해야 하냐라는 옵션을 생각하여 접근하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#해당 소스는 시간초과가 납니다.
cnts = []
 
N = int(input())
A = list(map(int, input().strip().split()))
B,C = map(int, input().strip().split())
 
# 1
for i in range(N):
    cnts.append(1)
 
# 2
for i in A:
    if (B-i) < 0:
        temp = abs(B-i)
        temp2 = temp // C
        if (temp % C) > 0:
            temp2 += 1
        cnts[A.index(i)] += temp2
# 3
print(sum(cnts))

1
2
3
4
5
6
7
8
9
10
11
12
13
14

N = int(input())
cnts = N
A = list(map(int, input().strip().split()))
B,C = map(int, input().strip().split())
 
for i in A:
    if (B-i) < 0:
        temp = abs(B-i)
        temp2 = temp // C
        if (temp % C) > 0:
            temp2 += 1
        cnts += temp2
 
print(cnts)