[백준 문제풀이] 얼렁뚱땅 3020번 개똥벌레 풀이
이거 골드5 문제인데 솔직히 문제 딱 보고 이게 왜 도대체 골드5 문제인지 이해하지 못했다.
왜냐면 정말 쉬워 보였기 때문이다.
첫번째 시도 : 메모리 초과
칼럼의 합을 계산할 수 있으니까 이런 방향으로 생각했다
근데 메모리 초과가 떠서 쪕 배열을 nxm 크기로 만드는 것은 안되겟다고 생각했다.
n, m = map(int,input().split())
array = []
for i in range(1,n+1) :
how_many = int(input())
if i%2 == 1 :
temp = [1]*how_many + [0]*(m-how_many)
array.append(temp)
else :
temp = [0] * (m - how_many) + [1] * how_many
array.append(temp)
col_array = list(zip(*array))
del array
min_ = n
count = 0
for col in col_array :
sum_ = sum(list(col))
if sum_ < min_ :
count = 1
min_ = sum_
elif sum_ == min_ :
count += 1
else :
continue
print(min_, count)
두번째 시도 : 시간초과
누적합을 해야겠다 생각했는뎁셔 생각이 짧았당 키키득
Prefixsum을 모르는 상태로 했다.
리스트끼리 한방에 빵 합쳐주는게 있으면 좋지만, 리스트는 for문을 통해 합쳐줘야해서 for문을 하나 더 했더니 시간초과가 떳나보다
여기서 생각한 누적합은 어떤거냐면 예를들어 석순이 3이라면
0번부터 2번까지 array에 1을 더해주는 방식이었다.
종유석이라면 쇼로롱해서 반대로 하는거고
석순이랑 종유석이랑 반대인가? 무튼 ㅋㅋ
n, m = map(int,input().split())
array = [0]*m
for i in range(1,n+1) :
how_many = int(input())
if i%2 == 1 :
for j in range(how_many) :
array[j] += 1
else :
for j in range(m-1,m-how_many-1,-1) :
array[j] += 1
min_ = min(array)
count = array.count(min_)
print(min_, count)
세번째 시도 : 통과(블로그 참조)
내 머리속으로는 누적합을 하는 법을 두번째 시도 밖에 안나와서 찾아봤다
Prefixsum을 이용해서 해야한다구 한다.
구간합 혹은 누적합을 구할 때 사용한다구 한다.
여기서 사용하는 누적합의 개념은 총 높이가 5고 석순의 크기가 4라면
4층에서 방해물의 개수는 5층에 있는 방해물 개수 + 4층의 방해물 개수 인거다
왜냐면 5층은 4층보다 높으니까 5층이면 무조건 4층에서도 걸릴 수 밖에 없는거다
만약 높이가 5고 석순의 크기가 3이면
5층에 있는 방해물 개수 + 4층의 방해물 개수 + 3층의 방해물 개수 인거다
그래서 일단 up과 down에 해당층이라는 종유석/석순 하나 잇슈 이렇게만 추가해주고
그 밑의 for문을 이용해서 누적합을 해준다.
웩.. 이런생각 어떻게 하는고야
누적합해주는 for문을 보면 그래서 배열의 끝에부터 1씩 감소하게 하는거고
만약 높이 5면
5층 갯수는 5층 갯수
4층 갯수는 5층 + 4층... 뭐 이렇게 해준다
흐힝 너무 어려엉
n, m = map(int,input().split())
up = [0]*(m+1)
down = [0] *(m+1)
min_ = n
count = 0
for i in range(n) :
if i % 2 == 0 :
down[int(input())] += 1
else :
up[int(input())] += 1
for i in range(m-1,0,-1) :
down[i] += down[i+1]
up[i] += up[i+1]
for i in range(1,m+1) :
if min_ > (down[i]+up[m-i+1]) :
min_ = down[i]+up[m-i+1]
count = 1
elif min_ == (down[i]+up[m-i+1]) :
count += 1
print(min_,count)
아~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 힝