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)
알고리즘 스터디 - 노션 기록
알고리즘 스터디
목표 : 1일 1알고리즘 문제 사용 언어 : Python3 / Oracle
mingxoxo.notion.site
'study > 알고리즘' 카테고리의 다른 글
[알고리즘/프로그래머스] 멀쩡한 사각형 (0) | 2022.03.02 |
---|---|
[알고리즘] 정렬 알고리즘 (0) | 2022.02.23 |
[알고리즘/프로그래머스] 가장 큰 수 (0) | 2022.01.26 |
[알고리즘/프로그래머스] Level 1 끝 ! (0) | 2022.01.11 |
[알고리즘/프로그래머스] 소수 찾기 (0) | 2022.01.07 |