python 백준 14620

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

로직

• 입력값으로 땅값이 주어짐
• 땅값을 기준으로 row,column 위치에 씨앗을 심을 경우 필요한 비용을 계산
• 계산된 비용을 정렬(낮은 비용부터 탐색 하기 위해)
• 3개의 값을 선택 후, 근처에 있는지(꽃 잎이 겹쳐 시드는지)를 체크
• 이를 이용하여 값 갱신, 갱신된 값으로 백트레킹

def costCheck(N:int,arr:list[list[int]])->list[tuple[int]]:
    newArr = list()
    for r in range(N):
        for c in range(N):
            num = arr[r][c]
            for nr,nc in ((r+1,c),(r-1,c),(r,c-1),(r,c+1)):
                if not (0<=nr<N and 0<=nc<N):
                    num = -1
                    break
                num += arr[nr][nc]
            if num != -1:
                newArr.append((num,r,c))
    newArr.sort()
    return newArr

def solution(N:int,arr:list[list[int]])->int:
    def isNear(arr1, arr2):
        r1, c1 = arr1[1], arr1[2]
        r2, c2 = arr2[1], arr2[2]
        if abs(r1 - r2) + abs(c1 - c2) <= 2: return True
        return False

    maxCost = 200
    ans = 16*maxCost
    ls = costCheck(N,arr)
    L = len(ls)

    for i in range(L-2):
        for j in range(i+1,L-1):
            if isNear(ls[i],ls[j]): continue
            num = ls[i][0] + ls[j][0]
            if num >= ans:break
            for k in range(j+1,L):
                if isNear(ls[i],ls[k]) or isNear(ls[j],ls[k]):continue
                totalNum = num + ls[k][0]
                if totalNum >= ans:break
                ans = totalNum
    return ans

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
ans = solution(N,arr)
print(ans)

개인적인 후기

• 오랜만에 푸는 알고리즘 문제라서 그런지 재밌었다.
• 어떻게 해야 연산을 줄일 수 있을지 고민하는 재미가 있었다.
  • dp 적용을 해야 하나 고민
  • 낮은 값 1,2,3번째를 계산하고 후에 2,3,4를 계산시 2+3에 해당 하는 연산이 반복해 일어나기에 기록해야 하나 고민
  • 코드가 가독성 문제도 있지만, 문제의 N이 그렇게 크지 않기에 기록에 필요한 연산과 큰 차이가 없다 + 메모리 낭비 라는 생각으로 보류
• 가독성에 대한 고민도 재밌었다
  • isNear 함수