[삼성 sw 2177] 홈 방범 서비스(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& 

SW Expert Academy

완전탐색유형.

어떻게하면 시간초과를 줄일까 고민하면서

어떤 좌표에서 bfs를 해줄지 고민하다가

해당 좌표마다 최대의 마름모를 만들고

계속 줄여나가는 방법이 베스트였습니다.

 

방범 서비스 영역을 보고

바로 bfs마려웠습니다.

그런데, bfs로 하면 

k=1부터 모든 경우를 다 구해야해는데

이러면 시간초과가 날 수 밖에 없습니다.

만약에 제가

k=1부터 점점 크게 크게 만들어서

손해를 보면 더이상 하지 않는 걸로 코드를 짰다 해보겠습니다.

이런 생각은

'더 커져봤자 비용만 더 늘어나지,

이득보겠어?'라는 단순한 생각이었습니다.

그런데 반례를 보시면

k=1일때는 적자를 봐도

k=2일때는 흑자를 보는

특이한 케이스가 발생합니다.

 

이 문제는 곰곰히 생각해보면

'손해 안보는 범위에서

서비스 가능한 총 집의 갯수'를 구하는 거라

집의 갯수만 받아내면 됩니다.

그러니 최대한 넓은 범위부터

점차 줄여나가면서

흑자를 볼 수 있는지 판단합니다.

마름모꼴을 직접 for문 돌리면서 구하면서 말이죠.

 

https://blog.naver.com/d2420/221969421384

[SWEA] 2117 홈 방범 서비스 C++

k의 범위에 대한 설명이 있는 코드입니다.

저는 테케랑 맞기위해 때려맞춘(?)경우인데

이분은 나름 근거를 가지고 설명해주셨네요.

def inside(x,y):
    if x<0 or x>=N or y<0 or y>=N:
        return False
    return True
def square(sx,sy):
    global answer
    for k in range(N+1,0,-1):

        cost=k*k+(k-1)*(k-1)
        cnt=0
        do=0
        for x in range(sx-k+1,sx+1):
            for y in range(sy-do,sy+do+1):

                if inside(x,y):
                    if room[x][y]==1:
                        cnt+=1
            do+=1
        do-=2
        for x in range(sx+1,sx+k):
            for y in range(sy-do,sy+do+1):

                if inside(x,y):

                    if room[x][y]==1:
                        cnt+=1

            do-=1


        if M*cnt-cost>=0:
            #print(k,cnt,cost,M*cnt)
            #print(sx,sy,k,M,M*cnt,cost)
            return cnt

    return 0

T=int(input())

for t in range(1,T+1):
    N,M=map(int,input().split())
    room=[list(map(int,input().split())) for _ in range(N)]
    answer=1


    for x in range(N):
        for y in range(N):
            answer=max(answer,square(x,y))
            #print(x,y,answer)
    print("#%d %d"%(t,answer))

 

범위만 보면 귀신같이 bfs를 쓰고 싶지만

때로는 다른 방법도 있다는 걸.

bfs를 써야할 때가 있고 

안쓸 때가 있다는 걸 공부하게 만들어준 좋은 문제입니다.