[C++] 백준 2579번 풀이 (계단오르기게임)

정민경·2023년 1월 3일
0

baekjoon

목록 보기
2/57
post-thumbnail

- 문제 (2579번) : 계단오르기 문제

  • 링크 : https://www.acmicpc.net/problem/2579

    다음과 같은 규칙을 만족할 때 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성.
    1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
      ( 바로 다음계단 혹은 다다음계단을 오를 수 있다. )
    2. 연속된 세 개의 계단을 모두 밟아서는 안된다.
      ( 단, 시작점은 계단에 포함되지 않는다. )
    3. 마지막 도착 계단은 반드시 밟아야 한다.

- 입력 및 출력

[입력]

  • 입력의 첫째 줄에는 계단의 개수가 주어짐. ( 계단의 개수 ≤ 300, 자연수 )
  • 둘째 줄부터 한줄에 하나씩 제일 아래에 놓은 계단부터 순수대로 각 계단의 점수가 주어짐. (계단의 점수 ≤ 10,000, 자연수)

[출력]

  • 게임을 통해 얻을 수 있는 총 점수의 최댓값을 출력

- 문제 풀이

  • 계단을 하나씩 오르며 max값 update <- DP 활용해 문제 해결
  • memoization을 할 때
    1. 계단이 1개일때 : 계단이 1개이므로 첫번째 계단이 max

    2. 계단이 2개일때 : 첫번째 계단 + 두번째 계단 점수가 max 점수
      (각 계단의 점수는 10,000 이하의 자연수이므로 성립됨.)

    3. 계단이 3개일때 :
      [첫번째 계단 + 세번째 계단] or [두번째계단 + 세번째 계단] 이 된다.
      ( 게임의 규칙 중 3개의 계단을 연속해 올라갈 수 없고, 마지막계단은 반드시 올라가야 하므로)

    4. 계단이 4개 이상일 때 : 계단이 4개일때를 생각해보면
      [두번째 계단 + 네번째 계단] or
      [첫번째 계단 + 세번째 계단 + 네번째 계단]
      이 된다.


      이것을 N개의 계단으로 생각해보면 다음과 같다.

      [N-2 계단까지의 max + N번째 계단] or
      [N-3 계단까지의 max + N-1번째 계단 + N번째 계단]

이 memoization을 통해 코드를 작성하면 다음과 같다.
( input.at(N) : N번째 계단의 점수 , maximum.at(N) : N까지의 최대점수)

  • 계단이 1개일때
  • 계단이 2개일때
  • 계단이 3개일때
  • 계단이 4개 이상일때

- 최종 코드

0개의 댓글