[알고리즘/백준] 21758번 꿀 따기

21758번 꿀 따기 - https://www.acmicpc.net/problem/21758

 

 

접근 방법

 

1. 무조건 꿀통은 끝에 있어야 한다.

--> 그래야 꿀벌이 지나가는 칸 수가 늘어난다.

 

2. 하나의 꿀벌은 맨 끝에서 출발한다.

--> 1번과 일맥상통

 

3. 꿀통이 왼쪽에 있냐 / 오른쪽에 있냐의 경우의 수 2가지 + 장소 칸이 3개일 경우

+ 장소 칸이 3개일 경우에는 중간 칸이 꿀통 위치가 될 수 있음

if len(honey_list) == 3:
    answer = max(2*honey_list[1], answer)

 

4. 또 다른 꿀벌의 모든 경우의 수는 반복문으로 해결

 

---

코드

 

- 처음에 서브태스크 4번 시간 초과

 

def honey(idx1, idx2, list_name):
    return sum(list_name[idx1:idx2])

N = int(input())
honey_list = list(map(int, input().split()))

honey_sum = sum(honey_list)
answer = 0

for i in range(1, N-1):
    answer = max(answer, honey_sum - honey_list[0] + honey(i+1, N, honey_list)- honey_list[i])
    answer = max(answer, honey_sum - honey_list[N-1] + honey(0, i, honey_list) - honey_list[i])

if len(honey_list) == 3:
    answer = max(2*honey_list[1], answer)

print(answer)

 

- 최종 코드

 

N = int(input())
honey_list = list(map(int, input().split()))

honey_sum = sum(honey_list)
honey_leftsum = honey_sum - honey_list[0]
honey_rightsum = honey_list[0]

answer = 0

for i in range(1, N-1):
    honey_leftsum -= honey_list[i]
    answer = max(answer, honey_sum - honey_list[0] + honey_leftsum - honey_list[i])
    answer = max(answer, honey_sum - honey_list[N-1] + honey_rightsum - honey_list[i])
    honey_rightsum += honey_list[i]


if len(honey_list) == 3:
    answer = max(2*honey_list[1], answer)

print(answer)

 

 

---

 

알고리즘 스터디 - 노션 기록

 

알고리즘 스터디