[3020] 개똥벌레 In python

 

누적합으로 먼저 접근하여

코드를 작성했다.

 

원하는 답이 나와서

아싸! 이러고 백준에 제출을 했는데

아니.. 시간초과요 .. ? 

 

python3로 했다가 시간초과가 떠서

pypy3로 돌려봤다.

 

응 역시 안된다.. ㅎ

똑같이 시간초과가 떠서

좀 고민하다가 

결국 구글링.. 

 

n, h = map(int, input().split())
array = [int(input()) for _ in range(n)]
# 짝수 - 석순, 홀수 - 종유석
answer = [0 for _ in range(h)]
for idx, now in enumerate(array):
    if idx % 2 == 0:  # 석순
        for i in range(0, now):
            answer[i] += 1
        continue
    else:  # 종유석
        for i in range(h - now, h):
            answer[i] += 1

result = [1000000000, 1]  # min 구별, cnt
for i in answer:
    if result[0] > i:
        result[0] = i
        result[1] = 1
    elif result[0] == i:
        result[1] += 1
    else:
        continue
print(*result)

---

 

예제 입력 1로 과정을 풀어서 이해해보았다.

 

내가 풀었던 방식은

석순의 크기가 4이면 높이 1부터 시작해서 4까지 누적합을 이용하여

각각 값을 더해주는 개념이었다.

 

따라서

시간 복잡도가 

N^2... ( 이중 반복문이 돌아가니까)

 

시간 복잡도를 계산하는 방법에 대해 알아보기

만약 N의 범위가 500인 경우

: 시간 복잡도가 O(N^3)인 알고리즘 설계시 문제 풀 수 있음.

 

만약 N의 범위가 2,000인 경우

: 시간 복잡도가 O(N^2)인 알고리즘 설계시 문제 풀 수 있음

 

만약 N의 범위가 100,000인 경우

: 시간 복잡도가 O(NlogN)인 알고리즘 설계시 문제 풀 수 있음

 

만약 N의 범위가 10,000,000인 경우

: 시간 복잡도가 O(N)인 알고리즘 설계 시 문제 풀 수 있음

 

 

파이썬은 1초에 1000만 정도라고 가정하고 생각하면 된다. 

 

 

위 문제는 범위가 1000만 정도니까?

O(N)인 알고리즘 이하로 설계를 해야 문제를 풀 수 있다.

 

근데 나는 N^2인 시간복잡도의 코드를 작성했으니

당연히 안되지 ㅎ

 

 

높이에 따라 석순과 종유석의 위치를

각각 리스트에 저장해준다.

 

 

석순은 1번, 3번, 5번 자리에 위치해있다.

그러면 down=[0,1,0,1,0,1,0,0] 

Down[0]은 인덱스 처리 상 필요해서 선언한 것일 뿐. 아무 역할이 없다.

 

이제 여기서 For문을 돌려서

각각의 석순이 어느 높이에 걸쳐있는지 살펴봐야한다.

 

이때는 For문을 배열의 끝부터 돌게끔 해야 한다. 

이 부분에서 사실 좀 막혔다.

왜 배열의 끝부터 돌려줘야하지? 했다.

 

down[높이]=석순의 개수

 

각각 1,3,5 높이의 석순이 있다

그러면 높이 1인 석순은 높이 1까지 자라있는거고

높이 3인 석순은 높이 1부터 3까지 자라있는거고

높이 5인 석순은 높이 1부터 5까지 자라있는거다.

 

 

그러면 높이 입장에서

높이 5에 걸쳐잇는 석순의 개수는 1 -> down[5]=1

높이 4에 걸쳐있는 석순의 개수 1 -> down[4]=0+down[5] 

석순의 높이가 5라면 4,3,2,1에 다 걸쳐있기 때문에

높이 3에 걸쳐 있는 석순의 개수 2 -> down[3]=1+down[4]

높이 2에 걸쳐있는 석순의 개수 2 -> down[2]=0+down[3]

높이 1에 걸쳐 있는 석순의 개수 3 -> down[1]=1+down[2]

 

 

이런식으로 For문을 2번 돌리지 않아도

배열의 인덱스 = 동굴의 높이

배열의 값 = 해당 인덱스(높이)에 걸쳐있는 석순의 개수

위 방식을 이용하면 값을 구할 수 있다!

 

 

 

down[i]=down[i]+down[i+1]

위 식을 적용하면

 

 

back=[0,3,2,2,1,1,0,0]이라는 값이 산출된다.

위 리스트가 의미하는 건

back[1]은 높이 1에 위치해있는 석순의 개수다.

 

n, h = map(int, input().split())
down = [0 for _ in range(h+1)]  # 석순
up = [0 for _ in range(h+1)]  # 종유석
for i in range(n):
    if i % 2 == 0:  # 석순
        down[int(input())] += 1 # int(input()) 높이에 석순이 있다는 걸 체크
    else:
        up[int(input())] += 1 # int(input()) 높이에 종유석이 있다는 걸 체크

for i in range(h - 1, 0, -1):
    up[i] += up[i + 1]
    down[i] += down[i + 1]


result = [1000000000, 1]  # min 구별, cnt
for i in range(1,h+1):
    if result[0] > up[h-i+1]+down[i]:
        result[0] = up[h-i+1]+down[i]
        result[1] = 1
        continue
    elif result[0] == up[h-i+1]+down[i]:
        result[1] += 1
print(*result)