[C] 1932: 정수 삼각형

이 문제 역시 Dynamic Programming! 역시 규칙찾아 점화식을 구하면 쉽게 풀 수 있다

 

규칙은 자기 위층의 양 옆까지 수까지의 경로에 있는 수의 합을 저장하는 것하면 되는데

여기서 주의해야 할 것은 각 층의 양끝은 무조건 바로 위쪽 한군데에서만 따로 내려오므로 점화식에서 예외처리를 해줘야한다. 예외처리를 굳이 하고 싶지 않다면 전에 풀었던 Knapsack Problem처럼 배열 양 끝에 0을 추가해주면 한번의 정리가 가능하다.

 

처음에 이 문제를 풀 때 잘못 이해하여 배열을 500!만큼 잡야아하는줄 알고 재귀함수를 이용해 각 함수를 호출할 때마다 배열의 크기가 최대 500만큼 되도록 잡았는데 사실 이차원배열을 이용하면 최대 250000의 크기를 잡아도 되어 범위였다! 그래서 이차원 배열을 잡고 for문을 이용해 푸는 것이 훨씬 이해하기 편한 방법이었다.

아래는 재귀를 이용해서 푼 소소크드다!

 

그리고 여기서 주의해야할 건 n=1일때 따로 결과값을 보여줘야한다!

아마 사람들이 못찾는 가장 중요한 반례일 것이다

#include <stdio.h>

void triangle(int n,int arr[],int dp[],int cur)
{
  if(cur==n+1)
  {
    int max=0;
    for(int i=0;i<n;i++)
      {
        if(dp[i]>max)
          max=dp[i];
      }
    printf("%d",max);
    return;
  }
  for(int i=0;i<cur;i++)
    {
      scanf("%d",&arr[i]);
    }
  int cpy_dp[502];
  for(int i=0;i<cur;i++)
    {
      if(i==0) //왼쪽 끝쪽일때
      {
        cpy_dp[i]=dp[0]+arr[i];
      }
      else if(i==cur-1) //오른쪽 끝일때
      {
        cpy_dp[i]=dp[cur-2]+arr[i];
      }
      else //둘중 하나 선택
      {
        cpy_dp[i]=dp[i-1]>dp[i]?dp[i-1]+arr[i]:dp[i]+arr[i];
      }
    }
 /* for(int i=0;i<cur;i++)
    {
      printf("%d ",cpy_dp[i]);
      
    }
  printf("\n");*/
  triangle(n,arr,cpy_dp,cur+1);
}

  int main(void)
  {
    int n;
    scanf("%d",&n);
    int first[501];
    scanf("%d",&first[0]);
    int dp[502];
    dp[0]=first[0];
    int cur=2;
    if(n>1)
      triangle(n,first,dp,cur);
    else
      printf("%d",dp[0]);

  }