''' 1. 일단 기준점이랑 경계의 길이를 정해야함 다 해보는 수 밖에 없지 않나? 백트래킹으로 조합을 먼저 만들어볼까? # x,y 결정하고 d1,d2로 넘어가면 된다 2. 그 다음엔 뭘 확인해야하지? 그 구역을 바탕으로 경계선을 만들어야지 경계선을 5로, 그리고 그 안에 있는 값도 다 5로 3. 그 다음에는 구역 별로 def check(new): sm1,sm2,sm3,sm4,sm5=0,0,0,0,0 v=[[0]*N for _ in range(N)] x,y,d1,d2=new[0],new[1],new[2],new[3] for r in range(N): for c in range(N): if 0 <= r < x+d1-1 and 0 <= c <= y-1: sm1+=arr[r][c] v[r][c]=1 elif 0 <= r <= x+d2-1 and y-1 < c <= N-1: sm2+=arr[r][c] v[r][c]=1 elif x+d1-1 <= r <= N-1 and 0 <= c < y-d1+d2-1: sm3+=arr[r][c] v[r][c]=1 elif x+d2-1 < r <= N-1 and y-d1+d2-1 <= c <= N-1: sm4+=arr[r][c] v[r][c]=1 for i in range(N): for j in range(N): if v[i][j]==0: sm5+=arr[i][j] mx= max(sm1,sm2,sm3,sm4,sm5) mn= min(sm1, sm2, sm3, sm4, sm5) print('-----') print(new) print(sm1, sm2, sm3, sm4, sm5) return mx-mn ''' def check(new): x, y, d1, d2 = new[0], new[1], new[2], new[3] if x+d1+d2<=N-1 and y < y+d2 <= N-1: sm1, sm2, sm3, sm4, sm5 = 0, 0, 0, 0, 0 v=[[0]*N for _ in range(N)] #print(x, y, d1, d2) for i in range(0,d1+1): v[x+i][y-i]=5 v[x+d2+i][y+d2-i]=5 for i in range(0,d2+1): v[x+i][y+i]=5 v[x+d1+i][y-d1+i] = 5 for row in v: if row.count(5)==2: s=row.index(5) for i in range(s+1,len(row)): if row[i]==5: break row[i]=5 for i in range(N): for j in range(N): if v[i][j] == 5: sm5 += arr[i][j] for r in range(N): for c in range(N): if r < x+d1 and c <= y and v[r][c]==0: sm1 += arr[r][c] v[r][c] = 1 elif r <= x+d2 and y < c and v[r][c]==0: sm2 += arr[r][c] v[r][c] = 2 elif x+d1 <= r and c < y-d1+d2 and v[r][c]==0: sm3 += arr[r][c] v[r][c] = 3 elif x+d2 < r and y-d1+d2 <= c and v[r][c]==0: sm4 += arr[r][c] v[r][c] = 4 mx = max(sm1, sm2, sm3, sm4, sm5) mn = min(sm1, sm2, sm3, sm4, sm5) else: return 40000 return mx - mn def btk_for_d2(cnt,new): global mn if cnt == 1: mn=min(mn,check(new)) return for d2 in range(1,N-new[1]): # 일단 인덱스 잘못됨 new.append(d2) btk_for_d2(cnt+1,new) new.pop() def btk_for_d1(cnt,new): if cnt == 1 : btk_for_d2(0,new) return for d1 in range(1,new[1]+1): new.append(d1) btk_for_d1(cnt+1,new) new.pop() def btk_for_y(cnt,new): if cnt == 1 : btk_for_d1(0,new) return for y in range(1,N-1): new.append(y) btk_for_y(cnt+1,new) new.pop() def btk_for_x(cnt,new): if cnt == 1 : btk_for_y(0,new) return for x in range(0, N - 2): new.append(x) btk_for_x(cnt+1,new) new.pop() N=int(input()) arr=[list(map(int,input().split())) for _ in range(N)] mn=40000 btk_for_x(0, []) print(mn)

제출 #30935

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: