[백준/1184/파이썬] 귀농

https://www.acmicpc.net/problem/1184

1184번: 귀농

Problem

• 현수 땅의 정보가 주어졌을 때, 땅을 나누어주는 방법의 수를 구하는 프로그램을 작성하시오. 

조건

• 상근이와 선영이는 도심 속의 삶에 싫증을 느꼈고, 친구 현수가 있는 시골로 농사를 지으려 내려왔다. 현수의 땅은 크기가 N×N 인 정사각형이고, 땅은 단위 정사각형 1×1로 나누어져 있다. 각 단위 정사각형 (i,j)의 수익은 Aij이다. Aij는 음수가 될 수도 있다. (땅을 경작하지 않아 관리가 필요한 경우)
• 현수는 자신의 땅의 일부를 상근이와 선영이에게 빌려주려고 한다(소작농??!). 두 사람이 받게되는 땅은 항상 직사각형 모양이고, 변은 축에 평행하다.
• 현수는 두 사람이 농사지을 땅의 수익의 합이 같게 되도록 땅을 빌려주려고 한다. 또, 경쟁심을 유도하기위해 두 땅은 꼭짓점 하나에서만 만나게 하려고 한다. (변을 공유할 수는 없다)

SOL

문제는 짧지만, 엄청 어려웠던 문제이다.우선 문제를 이해하는게 항상 제일 중요하다

 

현수가 꼭짓점을 기준으로, 상근이와 선영이에게 땅을 나눠주는 경우를 생각해보자.이 경우는 그림으로 그려보는게 훨씬 편하다.

이 외에도 사실 엄~청 경우가 많다.

 

위와 같이 한 꼭짓점에서 직사각형으로 땅을 나눠주는 경우는 엄청 많다.

그리고, 한 꼭짓점에 대해서 크게 2가지 경우가 생기게 된다.

1. 왼쪽 위 , 오른쪽 아래
2. 오른쪽 위,왼쪽 아래

해당 꼭짓점을 기준으로 직사각형을 만들면서 반복하는 반복문의 범위도 생각해줘야한다.

예를들어, 왼쪽 위를 계산한다고 하면, y는 감소하고, x도 감소하는 방향으로 반복을 돌아야한다.

두 사람이 농사지을 땅의 수익의 합이 같게 되도록 땅을 빌려주는 방법

만약, 시뮬레이션의 느낌으로 모든 경우를 구하게 된다면 무적권 TL이 발생할거 같아서, test를 해보았다.DP[24][24]가 최종 경우의 수이다. 94,163,002,754,652 900 가지가 나온다고 한다.940조이다(ㄸㄸㄷ)

DP = [[0 for _ in range(25)] for _ in range(25)]

#print(DP)

DP[0]=[x for x in range(1,26)]
#print(DP)

for i in range(1,25):
    DP[i][0] =i+1

for i in range(1,25):
    for j in range(1,25):
        DP[i][j]=DP[i-1][j] +DP[i][j-1]
for dp in DP:
    print(dp)

그렇다면, 시뮬레이션으로 모든 경우의 수를 보여주는건 불가능하다. 하지만, 내가 위에처럼 DP로 경우의수를 구하는것과 같이, DP로 두 사람이 농사지을 땅의 수익의 합이 같게 되도록 땅을 빌려줄 수 없을까? 2중 반복을 한다고 생각했을 때, 처음 반복할 때는, 누적합을 그냥 넣어주면 되고, 두번째 반복부터 DP에 저장된 값 + 누적합을 해주면 된다. 

 

정리를 하자면,크게 2가지 경우를 볼거고

1. 왼쪽위, 오른쪽 아래 
   • 꼭짓점은 N*N 보드이면, N-1*N-1로 반복이 된다.(grid ->area) 이걸 난 보통 좌표가 방이 됬을때, 변화라고 말한다.(사실, 세어보면된다. 3*3이면 위 조건에 맞게 나오는 꼭짓점은 4개뿐이다)
   • 해당 꼭짓점를 기준으로 직사각형을 만들면서 계산하는 반복문의 범위도 생각해줘야한다.
   • 누적합을 비교하는건 좋으나, 그 누적합을 하나하나 다 봐야한다.(경우의 수를 구하는거이므로, 누적합이 같은 경우를 다 봐야한다) => 누적합을 저장하는 sum이라는 배열을 따로 선언해줬음.
2. 왼쪽 아래, 오른쪽 위
   • 사실 똑같은 작업이다.

# 귀농
# DP,누적합 or 시뮬레이션
# 우선은 구현으로 가보자.
import sys
input = sys.stdin.readline
N= int(input())

board=[list(map(int,input().split())) for _ in range(N)]
DP = [[0 for _ in range(51)] for _ in range(51)]
sum1=[]
sum2=[]
def calLeftUp(y,x):
    for i in range(y,-1,-1):
        total=0
        for j in range(x,-1,-1):
            total+=board[i][j]
            if i !=y:
                DP[i][j] = DP[i+1][j]+total
            else:
                DP[i][j]= total
            sum1.append(DP[i][j])
                
def calRightDown(y,x):
    for i in range(y,N):
        total=0
        for j in range(x,N):
            total+=board[i][j]
            if i !=y:
                DP[i][j] = DP[i-1][j]+total
            else:
                DP[i][j]= total
            sum2.append(DP[i][j])

def calRightUp(y,x):
    for i in range(y,-1,-1):
        total=0
        for j in range(x,N):
            total+=board[i][j]
            if i !=y:
                DP[i][j] = DP[i+1][j]+total
            else:
                DP[i][j]= total
            sum1.append(DP[i][j])

def calLeftDown(y,x):
    for i in range(y,N):
        total=0
        for j in range(x,-1,-1):
            total+=board[i][j]
            if i !=y:
                DP[i][j] = DP[i-1][j]+total
            else:
                DP[i][j]= total
            sum2.append(DP[i][j])
def solve():
    ans=0
    for i in range(N-1):
        for j in range(N-1):
            calLeftUp(i,j)
            calRightDown(i+1,j+1)
            
            for s1 in sum1:
                for s2 in sum2:
                    if s1 ==s2:
                        ans+=1
            #누적합 부분을 지워줘야한다.
            sum1.clear()
            sum2.clear()
            
            calRightUp(i,j+1)
            calLeftDown(i+1,j)
            for s1 in sum1:
                for s2 in sum2:
                    if s1 ==s2:
                        ans+=1
            sum1.clear()
            sum2.clear()
    print(ans)

solve()

밑의 분 C++코드를 참고해서, Python으로 짜보았습니다.

 

참고 블로그

https://injae-kim.github.io/problem_solving/2020/02/22/baekjoon-1184.html

Injae's devlog