[백준] 2579.cpp : 계단 오르기

www.acmicpc.net/problem/2579

2579번: 계단 오르기

#include <iostream>

int stair[301];

int big(int a, int b)
{ return (a >= b ? a : b); }

int main(void)
{
  int n;
  std::cin >> n;
  int data;
  for(int i = 1 ; i <= n ; i++)
  {
    std::cin >> data;
    stair[i] = data;
  }
  // 한 칸 올라왔을 떄의 점수에 대한 배열
  int up1[301] = {0, stair[1], stair[1] + stair[2]};
  // 두 칸 올라왔을 때의 최댓값 점수에 대한 배열
  int up2[301] = {0, 0, stair[2]};

  for(int i = 3 ; i <= n ; i++)
  {
    // 한 칸 올라왔을 때는 전에 한 칸 올라왔을 수 없기 때문에, 두 칸 올라온 최고점에서 현재 점수를 더함
    up1[i] = stair[i] + up2[i - 1];
    // 두 칸 올라왔을 경우엔 전에 몇 칸 올라왔는지 상관 없기 때문에, 둘 중 최고점에서 현재 점수를 더함
    up2[i] = stair[i] + big(up1[i - 2], up2[i - 2]);
  }
  // 마지막 칸 올라왔을 때의 최고점
  std::cout << big(up1[n], up2[n]) << '\n';
}  

 

[Approach]

1. 재귀로 모든 가능성 검색해보기 (완전탐색?) 너무 많이 걸릴 것 같긴 하다. -> 답은 맞는 것 같은데 시간초과가 난다.

2. 다이나믹 프로그래밍이 될까?  잘만 응용하면 DP 배열 만들수도 있을 것 같다.

     분할 정복의 느낌으로 접근해보자

 

[Point]

1. 굉장히 시간을 많이 사용했지만 풀어냈을 때 짜릿했다. 그런데 밑에 보니 정보올림피아드 "초등부" 문제였다 ㅎㅎㅎ 현타오네

2. 굳이 DP 배열을 두개를 나눠서 만들 필요가 없어 보인다. 두개일 때야 어차피 i - 2 번째에서 가져오기 때문에 하나여도 되는데, 하나

     오를 때는 직전이 무조건 두칸이어야된다는 점을 DP[i - 3] + stair[i - 1] 로 표현할 수 있기 때문이다. 이게 훨씬 나은듯..

 

[More]

1. 기인이 한 분 계신다. 언젠간 저 코드를 이해할 날이 올까? (20465000)

 

 

+ 아래는 재귀 사용했을 경우에 대한 재귀함수이다. 버리기 아까워서 올려봤음

// 재귀로 전부 다 돌려볼 경우
int stepF(int curStair, int step)
{
  // 도착점부터 시작해서 한칸 내려갈지 두칸 내려갈지 결정
  // 다 내려올 경우의 리턴값
  if(curStair < 1) return 0;
  // 한 칸 내려갈 경우
  if(step == 1)
  {
    // 한칸 내려온 상태에서는 무조건 두 칸 내려가야함
    return stair[curStair] + stepF(curStair - 2, 2);
  }
  else
  {
    // 두칸 내려온 상태에서는 둘 중 최고값을 선택해서 내려감
    int p1 = stepF(curStair - 1, 1);
    int p2 = stepF(curStair - 2, 2);
    return stair[curStair] + (p1 >= p2 ? p1 : p2);
  }
}