다이나믹 프로그래밍 (Dynamic Programming) (3) - 실전문제 8.3) 개미 전사

2023. 8. 22. 14:12· Algorithm

문제)

N개의 식량 창고에 대한 정보를 입력받는다. 이 때 입력받은 순서대로 식량 창고가 인접해 있다고 생각한다. 개미 전사는 일직선 상에 존재하는 식량 창고 중에서 서로 인접하지 않은, 즉 최소한 한 칸 이상 떨어진 식량 창고들을 약탈할 수 있다. 이 때 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

입력조건)

  • 첫째 줄에 식량창고의 개수 N이 주어진다. (3 <= N <= 100)
  • 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000)

출력조건)

  • 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

입력예시)

4

1 3 1 5

출력예시)

8


풀이)

이 문제 또한 앞의 실전 문제와 동일하게 바텀업 방식으로 간단하게 해결할 수 있다. 바텀업 방식의 핵심인 결과 리스트를 생성하고 모든 값을 0으로 초기화한다. 이 후 입력받은 N개의 식량 창고에 대한 정보를 반복문을 통해 첫번째 인덱스부터 확인하며 결과 리스트에 값을 채울 것이다. 이 때 중요한 제한이 인접하지 않은 식량 창고를 침략해야 한다는 것이기 때문에 두 가지 경우가 생기게 된다. 

  1. 반복문의 (현재 인덱스-1) 을 침략한 경우 => 현재 인덱스는 침략할 수 없다. => 결과 리스트[i-1]
  2. 반복문의 (현재 인덱스-2) 를 침략한 경우 => 현재 인덱스를 침략할 수 있다. => 결과 리스트[i-2] + 입력 리스트[i]

위의 두 가지 경우의 최댓값을 결과 리스트의 현재 리스트에 저장하면서 결과 리스트를 채워 나가면 문제를 해결할 수 있다. 최종적으로 입력받은 N 번째 인덱스의 값이 원하는 문제의 답이 된다.

 

저작자표시 변경금지 (새창열림)

'Algorithm' 카테고리의 다른 글

다이나믹 프로그래밍 (Dynamic Programming) (5) - 실전문제 8.5) 효율적인 화폐 구성  (0) 2023.08.22
다이나믹 프로그래밍 (Dynamic Programming) (4) - 실전문제 8.4) 바닥 공사  (0) 2023.08.22
다이나믹 프로그래밍 (Dynamic Programming) (2) - 실전문제 8.2) 1로 만들기  (0) 2023.08.22
다이나믹 프로그래밍 (Dynamic Programming) (1) - 다이나믹 프로그래밍이란?  (0) 2023.08.21
이진 탐색 (Binary Search) (3) - 실전문제 7.3) 떡볶이 떡 만들기  (2) 2023.08.05
'Algorithm' 카테고리의 다른 글
  • 다이나믹 프로그래밍 (Dynamic Programming) (5) - 실전문제 8.5) 효율적인 화폐 구성
  • 다이나믹 프로그래밍 (Dynamic Programming) (4) - 실전문제 8.4) 바닥 공사
  • 다이나믹 프로그래밍 (Dynamic Programming) (2) - 실전문제 8.2) 1로 만들기
  • 다이나믹 프로그래밍 (Dynamic Programming) (1) - 다이나믹 프로그래밍이란?
공대생안씨
공대생안씨
전자공학과 학부생의 코딩 일기
티스토리
|
로그인
공대생안씨
공대생의 코딩 일기
공대생안씨
글쓰기
|
관리
전체
오늘
어제
  • All Categories (153)
    • Spring Boot (46)
      • JPA (7)
      • Lombok (2)
    • Java (21)
    • DevOps (3)
      • CI,CD (8)
      • Monitoring (2)
    • Database (7)
      • MySQL (5)
      • MongoDB (1)
      • H2 (1)
    • Trouble Shooting (5)
    • FE (4)
    • IntelliJ (3)
    • Git (3)
    • Algorithm (41)

블로그 메뉴

  • 홈
  • 태그
  • Github

공지사항

인기 글

hELLO · Designed By 정상우.v4.2.2
공대생안씨
다이나믹 프로그래밍 (Dynamic Programming) (3) - 실전문제 8.3) 개미 전사
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.