[파이썬] SWEA 5644 : 무선 충전 (TEST)

[파이썬] SWEA 5644 : 무선 충전 (TEST)

• SWEA 5644 : 무선 충전

---

풀이

방향성 생각

• 각 좌표에 들어가는 배터리를 어떻게 관리하냐가 관건이다.
• 각 좌표마다 최대 2개를 선택하는것이 맞다.
• 또한, 사람 두명이서 같은 영역에 있으면 서로 다른 무선 충전기를 이용하는 것이 핵심.
• 각 좌표에 어떤 무선 충전기가 들어갔냐는 bit로 관리했다.
• 사실 그리디하게 안풀어도 바로 풀리는 문제라서 효율적으로 풀지는 않았다.

 

전체코드

inside = lambda x,y : 0<=x<10 and 0<=y<10
dires = [(0,0),(0,-1),(1,0),(0,-1),(-1,0)]

def move(cmd : int, array : list) -> list:
    if cmd == 0: return array
    elif cmd == 1: return [array[0],array[1]-1]
    elif cmd == 2: return [array[0]+1,array[1]]
    elif cmd == 3: return [array[0],array[1]+1]
    elif cmd == 4: return [array[0]-1,array[1]]

TC = int(input())
for tc in range(1,TC+1):

    N = 10
    M,A = map(int,(input().split()))

    move_A = [0] + list(map(int,input().split()))
    move_B = [0] + list(map(int,input().split()))

    arr = [[0]*10 for _ in range(10)]

    charger = [tuple(map(int,input().split())) for _ in range(A)] # x,y,c.p
    # charger 정보 arr에 bit로 기록하기
    for idx,(x,y,c,p) in enumerate(charger,start=1):
        x,y = x-1,y-1
        for i in range(y-c,y+c+1):
            for j in range(x-c,x+c+1):
                if inside(j,i) and (abs(j-x) + abs(i-y) <= c):
                    arr[i][j] = arr[i][j] | (1<<idx)

    cur_A = [0,0]
    cur_B = [9,9]

    answer = 0

    # move queries
    for cmd_A,cmd_B in zip(move_A,move_B):

        # move
        cur_A = move(cmd_A,cur_A)
        cur_B = move(cmd_B,cur_B)

        # new loc state
        state_A = arr[cur_A[1]][cur_A[0]]
        state_B = arr[cur_B[1]][cur_B[0]]

        # 같은 BC를 공유하는 경우
        if state_A&state_B:
            temp = 0
            for i in range(1,A+1):
                if state_A&(1<<i): # A가 사용 가능한 charger를 사용 할 때
                    for j in range(1,A+1):
                        if state_B&(1<<j): # B가 사용 가능한 charger를 사용할 때
                            if i!=j:
                                temp = max(temp,charger[i-1][3]+charger[j-1][3])
                            else:
                                temp = max(temp,charger[i-1][3])
            answer += temp

        # 독립된 BC / 빈칸에 있는 경우 : 각 사람이 최대로 얻을 수 있는 charger 사용
        else:
            max_A = 0
            max_B = 0
            for i in range(1,A+1):
                if state_A&(1<<i):
                    max_A = max(max_A,charger[i-1][3])
                if state_B&(1<<i):
                    max_B = max(max_B,charger[i-1][3])
            answer += max_A + max_B

    print(f"#{tc} {answer}")

코멘트

• .