Maximum sum

분류없음 2008/04/09 14:11 |
문제 페이지
 
귀차니스트 님이 푸신 답을 조금 개선해 봤다.

자동채점 기준으로 수행 시간이 0.4초 정도 줄었다.

#include <stdio.h>

short m[101][101][101][101]={};

int main(void) {
 int rsum, lsum, nrsm, nlsm;
 int si, sj, ei, ej, size,i,j;
 int maxsum = -2000000;
 
 scanf("%d", &size);

 for (i=1; i<=size; i++)
 {
  for (j=1; j<=size; j++)
  {
   scanf("%d", &m[i][j][i][j]);
  }
 }
 for (si=1; si<=size; si++)
 {
  for (sj=1; sj<=size; sj++)
  {
   for (ei=si; ei<=size; ei++)
   {
    for (ej=sj; ej<=size; ej++)
    {
     if (sj == ej && m[si][sj][ei][ej] != 0)
     {
      nrsm = m[si][ej][ei][ej];
     }
     else 
     {
      rsum = m[si][sj][ei][ej-1];
      lsum = m[si][ej][ei-1][ej];
      nlsm = lsum + m[ei][ej][ei][ej];
      m[si][ej][ei][ej] = nlsm;
      nrsm = rsum + nlsm;
      m[si][sj][ei][ej] = nrsm;
     }
          
     if (maxsum < nrsm)
      maxsum = nrsm;
    }
   }
  }
 }
 
 printf("%d\n", maxsum);
 return 0;
}

시작위치, 끝위치로 로프를 돌리는 것보다
시작위치, 서브매트릭스의 사이즈에 대해서 루프를 돌리는 것이
중간결과를 더 많이 활용할 수 있을 것 같은데 아직 구현을 못하겠다.
Trackback 1 : Comment 1

Trackback Address :: http://walcure.tistory.com/trackback/100 관련글 쓰기

  1. Subject: Valladolid Online-judge.uva.es problem num. 108 :: Maximum sum problem. solved.

    Tracked from Lonewolf's story :: Awaken the giant! 2008/06/06 21:04  Delete

    #include <stdio.h> int main() { int n, iInnerCnt, iOuterCnt, iTempCnt, max; int matrix[100][100], temp[100]; scanf("%d", &n); max = 0; for (iInnerCnt = 0; iInnerCnt < n; iInnerCnt++) { scanf("%d", &matrix[0][iInnerCnt]); if (matrix[0][iInnerCnt] > max)..

댓글을 달아 주세요

  1. Lonewolf dlbo 2008/05/26 02:40 Address Modify/Delete Reply

    Maximum sum 문제를 풀려고 돌아다니다 봤습니다. 단순 노가다성으로 돌려보니 TL이 되어버리는군요 ㄱ-; 소스에 4차원 배열을 써 두셨는데 어떤 방식으로 돌리는건가요?