글 읽기 - 2차원 배열 prefix sum을 이용했는데 답이 도출이 안되네요

kkw564 8년 전 1

틀렸습니다라고 뜨는데 도와주시면 감사하겠습니다..

어느부분이 틀린지 정확히 감이 안오네요

#include <stdio.h>

int map[1026][1026] = {0,};
int tmp[1026][1026] = {0,};
int sum[1026][1026] = {0,};

int main()
{
 int n,m;
 int w,x,y,c,x1,x2,y1,y2;
 int i,j,t;
 int check = 0;
 
 scanf("%d %d",&n,&m);
 
 for(i = 1 ; i <= n ; i ++) // nxn 배열 입력 
 {
  for(j = 1; j <= n ; j ++) 
  {    
   scanf("%d",&map[i][j]);  
   if(j == 1)
   {
     sum[i][j] = sum[i-1][n] + map[i][j]; // prefix sum   
   }
   else
   {
    sum[i][j] = sum[i][j-1] + map[i][j]; // prefix sum
   }
  }   
 }
 /* // prefix sum 확인 
 for(i = 1; i <= n; i++)
 {
  for(j = 1; j <= n ; j ++)
  {
        printf("%d ",sum[i][j]);
  }
  printf("\n");
 }
 */
 
 for(t = 0; t < m; t ++) // m 횟수만큼 
 { 
  scanf("%d",&w); // w가 1인지 0인지 먼저 판별 
  if(w == 0)
  {
   scanf("%d %d %d",&x,&y,&c); // x,y,c를 받고
   
   tmp[x][y] = map[x][y];
   map[x][y] = c; // c로 바꿔준다.  
   
   check = 1; 
  }
  
  else if(w == 1)
  {
   scanf("%d %d %d %d",&x1,&y1,&x2,&y2); // 출력 범위
   
   if(check == 1 && x1 <= x && x <= x2 && y1 <= y && y <= y2)
   {
    for(i = x1; i <= x2; i++)
    {
      tmp[0][0] = tmp[0][0] + sum[i][y2] - sum[i][y1-1];    
    }        
    
    printf("%d\n",tmp[0][0] - tmp[x][y] + map[x][y]);
    tmp[0][0] = 0;
    check = 0;
   }
   
   else
   {
    for(i = x1; i <= x2; i++)
    {
      tmp[0][0] = tmp[0][0] + sum[i][y2] - sum[i][y1-1];    
    }
    printf("%d\n",tmp[0][0]);   
    tmp[0][0] = 0;
   }
    
  }
 
 }
    
    return 0; 
    
}

baekjoon 8년 전 0

2차원 배열은

S[i][j] = S[i-1][j-1] + S[i-1][j] + S[i][j-1] + A[i][j] 를 이용해서 해야 합니다.

ntopia 8년 전 1

음.. 이 문제는 중간에 수의 변경이 일어나는데,

prefix sum을 이용하려면 수가 변경될때마다 prefix sum 배열 전체를 업데이트 해야합니다

그래서 다른 방법이 필요합니다

ntopia 8년 전 0

구현하신 소스 내에서 예를 들어보면

(1,1)의 값을 변경하면 sum 배열 전체를 업데이트해야 바른 결과를 내겠죠

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2차원 배열 prefix sum을 이용했는데 답이 도출이 안되네요

kkw564 8년 전 1

baekjoon 8년 전 0

ntopia 8년 전 1

ntopia 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말