본문 바로가기
SWEA

[SWEA] 1252. 단순도금비용 (python)

by 콩순이냉장고 2024. 12. 9.

문제 URL : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Tx9aARECFAYD&categoryId=AV15Tx9aARECFAYD&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

문제 접근법 : 

생각하는데 좀 걸리는 문제였습니다. 그냥 좌상단에서 우하단까지 

검색해서 도금비용을 최소로 맞추도록 도금하는게 최선이기때문에 

범위가 3범위내에는 a가 5개이상이면 도금하고 2범위라면 a가 2개이상일때

범위가 1이라면 1개이상일때 도금을해야합니다.

그치만 좌상단 부터 우하단을 조사할때 방금말한 조건대로 단순히 제거한다면

 

예제의문제에선

이렇게

 

파란색 선처럼 도금되어서 도금의비용이 최소가 되질않습니다.

 

 

그렇다면 어떻게 최소로 맞출까 더생각을 해봤지만 범위를 3에서 1까지 다조사한후

a의 개수가 많고 범위의 개수가 높은걸 먼저 제거하면 어떨까? 생각했는데

범위가 3일때 a의 개수가 가장많은건 (3,4)의 범위가3인 9개를 먼저제거하면 되는구나 싶어 정렬을 생각해봤더니 pq를 이용하면 된다는걸 알았기에 해당 조건대로 풀어보니 맞더군요

 

 

소스코드:

import sys
import heapq
#sys.stdin = open("input.txt","r")
input = sys.stdin.readline

Test = int(input())
price =[0,1,2,5]

def getCnt(y,x,size):
    global board,n
    cnt = 0
    for i in range(y,y+size):
        for j in range(x,x+size):
            cnt+=board[i][j]
    return cnt
def cover(y,x,size):
    global board,n
    for i in range(y,y+size):
        for j in range(x,x+size):
            board[i][j]=0
for test in range(1,Test+1):
    n = int(input())
    m = int(input())
    board =[[0]*(n+5) for i in range(n+5)]
    l = list(map(int,input().split()))
    pq = []
    for i in range(0,m*2,2):
        board[l[i]][l[i+1]]=1

    for size in range(3,0,-1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                cnt = getCnt(i,j,size)
                if cnt>0 and cnt>=price[size]:
                    heapq.heappush(pq,(-cnt,-size,i,j))
    res= []    
    while pq:
        cnt,size,y,x = heapq.heappop(pq)
        cnt=-cnt
        size = -size
        newcnt = getCnt(y,x,size)
        if newcnt==cnt:
            cover(y,x,size)
            res.append((y,x,size))
        elif newcnt>0:
            for length in range(size,0,-1):
                newcnt = getCnt(y,x,length)
                if newcnt> 0 and newcnt>=price[length]:
                    heapq.heappush(pq,(-newcnt,-length,y,x))
    
    print("#{} {}".format(test,len(res)),end=' ')
    for i in range(len(res)):
        print("{} {} {}".format(res[i][0],res[i][1],res[i][2]),end=' ')
    print()

 

 

궁금한점 혹은 모르는점 혹은 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.