[SWEA 5644] 무선 충전

접근

두 명의 사용자가 이동을 할 때마다 주위에 충전할 수 있는 충전기를 모두 찾는다. 찾은 후에 성능을 기준으로 내림차순 정렬하여 두 명의 사용자가 최댓값이 되도록 충전기를 선택하도록 한다.

만약 같은 충전기 내에 두 명이 존재하면 배분을 해서 가져가야한다. 하지만 한 명이 다른 충전기 범위 내에도 존재하면 이 사용자는 다른 충전기를 선택하도록 해야한다.

 

구현

- 사용자 2명의 이동 경로를 move_info에 저장한다.

- 충전기의 정보를 charge_info에 저장한다.

- 이제 사용자들을 move_info에 기반하여 이동시키고

- 이동시킬 때마다 charge 함수로 위치를 보내서 최댓값으로 충전할 수 있는 양을 구한다.

for tc in range(test_case):
    N = 10
    M, A = map(int, input().split())
    move_info = [list(map(int, input().split())) for _ in range(2)]
    charge_info = []
    for a in range(A):
        x, y, c, p = map(int, input().split())
        charge_info.append([y, x, c, p, a+1])

    dy = [0, -1, 0, 1, 0]
    dx = [0, 0, 1, 0, -1]
    answer = charge(1, 1, N, N)
    ay, ax, by, bx = 1, 1, N, N
    for d in range(M):
        ay += dy[move_info[0][d]]
        ax += dx[move_info[0][d]]
        by += dy[move_info[1][d]]
        bx += dx[move_info[1][d]]
        answer += charge(ay, ax, by, bx)

    print("#{} {}".format(tc+1, answer))

- 두 명의 사용자들을 각각 충전기의 위치와 비교하여 c 이하일 때 충전할 수 있는 충전기의 리스트에 추가한다.

- 충전기 탐색이 종료되고 성능 순으로 내림차순 정렬한다.

- 먼저 A사용자가 충전기를 선택한다. 아래와 같이 for문으로 한 이유는 주위에 충전기가 없을 수도 있기 때문이다.

- 그 다음 A가 사용하지 않은 배터리 중에 최대 성능을 갖는 배터리를 B가 선택하도록 하여 두 개의 성능을 더한다.

- 이제 B가 먼저 선택하도록 하여 위의 과정을 반복한다.

- temp_a와 temp_b 중 최댓값을 반환하도록 한다.

def charge(ay, ax, by, bx):
    charge_a_list = []
    charge_b_list = []
    for y, x, c, p, n in charge_info:
        if abs(ay - y) + abs(ax - x) <= c:
            charge_a_list.append([p, n])
        if abs(by - y) + abs(bx - x) <= c:
            charge_b_list.append([p, n])

    charge_a_list.sort(key=lambda x: -x[0])
    charge_b_list.sort(key=lambda x: -x[0])

    temp_a = 0
    flag = 0
    for p, n in charge_a_list:
        temp_a += p
        flag = n
        break

    for p, n in charge_b_list:
        if n != flag:
            temp_a += p
            break

    temp_b = 0
    flag = 0
    for p, n in charge_b_list:
        temp_b += p
        flag = n
        break

    for p, n in charge_a_list:
        if n != flag:
            temp_b += p
            break

    return max(temp_a, temp_b)

---

전체 코드

test_case = int(input())

def charge(ay, ax, by, bx):
    charge_a_list = []
    charge_b_list = []
    for y, x, c, p, n in charge_info:
        if abs(ay - y) + abs(ax - x) <= c:
            charge_a_list.append([p, n])
        if abs(by - y) + abs(bx - x) <= c:
            charge_b_list.append([p, n])

    charge_a_list.sort(key=lambda x: -x[0])
    charge_b_list.sort(key=lambda x: -x[0])

    temp_a = 0
    flag = 0
    for p, n in charge_a_list:
        temp_a += p
        flag = n
        break

    for p, n in charge_b_list:
        if n != flag:
            temp_a += p
            break

    temp_b = 0
    flag = 0
    for p, n in charge_b_list:
        temp_b += p
        flag = n
        break

    for p, n in charge_a_list:
        if n != flag:
            temp_b += p
            break

    return max(temp_a, temp_b)

for tc in range(test_case):
    N = 10
    M, A = map(int, input().split())
    move_info = [list(map(int, input().split())) for _ in range(2)]
    charge_info = []
    for a in range(A):
        x, y, c, p = map(int, input().split())
        charge_info.append([y, x, c, p, a+1])

    dy = [0, -1, 0, 1, 0]
    dx = [0, 0, 1, 0, -1]
    answer = charge(1, 1, N, N)
    ay, ax, by, bx = 1, 1, N, N
    for d in range(M):
        ay += dy[move_info[0][d]]
        ax += dx[move_info[0][d]]
        by += dy[move_info[1][d]]
        bx += dx[move_info[1][d]]
        answer += charge(ay, ax, by, bx)

    print("#{} {}".format(tc+1, answer))