[C] 2579: 계단 오르기

이 문제도 역시 배열에 저장을 해가며 점화식을 구하기 위해 노력하였다.

 

먼저 각 계단마다 점수를 저장하는 score배열을 정의하고 각 단계마다 가장 높은 점수를 저장하는 arr배열을 정의하였다.

 

그리고 초기, 계단을 2개 오르기까지의 경우는 for문이 아닌 직접 배열에 저장하는 방식을 택했고 (어떤 방법으로 for문을 구성할지 감을 잡기위해서 & 초기값은 직접 정해줘야함) for문에서는 연속된 3개가 되는지에 따라 if문을, 그리고 각각의 if문에서 2계단을 뛰어넘는게 이득인지 1계단을 뛰어넘는게 이득인지 판별해 arr배열에 저장하였다.

 

그리고 이때 이차원 배열을 이용한 이유는 연속된 3개의 계단을 오른지 판별하기 위해서였다.

소스코드는 아래와 같다.

#include <stdio.h>

int main(void)
{
  int n;
  scanf("%d",&n);
  int score[n]; //계단의 점수 저장
  int arr[2][n]; //각 단계마다 최적의 점수를 저장 & 연속된 세수인지 확인
  for(int i=0;i<n;i++) //초기화
    {
      arr[0][i]=0;
    }
  for(int i=0;i<n;i++)
    {
      scanf("%d",&score[i]);     
    }
  
  arr[1][0]=score[0];
  arr[1][1]=score[1]+score[0];
  arr[0][0]=1;
  if(n>1) //이 조건을 넣지 않으면 n=1일때 자꾸 오류가 남(어차피 일차원배열로 생각해서 똑같은듯?)
    arr[0][1]=2;
  arr[1][2]=score[0]>score[1]?score[0]+score[2]:score[1]+score[2];
  if(score[0]>score[1])
  {
    arr[0][2]=1;
    
  }
  else
  {
    arr[0][2]=2;
    
  }
// printf("dd%d\n",arr[1][0]);
 // printf("2: %d",arr[1][2]);
  for(int j=3;j<n;j++)
    {
      if(arr[0][j-1]==2) //연속된 3개가 될 수도 있는경우
      {
        if(arr[1][j-2]>arr[1][j-3]+score[j-1]) //2계단 뛰어넘는게 이득
        {
          arr[0][j]=1;
          arr[1][j]=arr[1][j-2]+score[j];
        }
        else //연속된 두계단이 이득
        {
          arr[0][j]=2;
          arr[1][j]=arr[1][j-3]+score[j-1]+score[j];
        }
      }
      else //연속된 3개가 될 수 없는 경우
      {
        if(arr[1][j-1]>arr[1][j-2]) //연속된게 더 이득
        {
          arr[0][j]=2;
          arr[1][j]=arr[1][j-1]+score[j];
        }
        else //2계단 뛰어넘는게 더 이득
        {
          arr[0][j]=1;
          arr[1][j]=arr[1][j-2]+score[j];
        }
      }
     // printf("%d: %d\n",j,arr[1][j]);
    }
  printf("%d",arr[1][n-1]);

   
  
}

이를 조금 더 간단히 정리한 소스는 나중에 또 올릴려고 한다!