<보기>는 막대 자르기(rod cutting) 문제의 재귀적… | [9급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

<보기>는 막대 자르기(rod cutting) 문제의 재귀적 의사코드(pseudo code)이다. 막대의 길이 정수 $n$과 가격 배열 $p$를 입력 받아, 막대를 잘랐을 때 가능한 이익의 최댓값을 구한다. 이때, (가)에 들어갈 내용으로 가장 옳은 것은? (단, 배열 $p$의 길이는 $n$이며, $p[i]$는 길이가 $i$인 막대의 가격이다.)
CUT_ROD(p,n)
    if n==0
      return 0
    q=-∞
    for i=1 to n
      q=max{q,p[i]+      (가)      }
    return q

CUT_ROD(p,i-1)

CUT_ROD(p,i)

CUT_ROD(p,i+1)

CUT_ROD(p,n-i)