[SWEA] 무선 충전

https://swexpertacademy.com/main/main.do

SW Expert Academy

풀이

사용자와 BC의 거리를 계산해서 충전할 수 있는지 판단하고 충전할 수 있다면 어떤 BC를 선택하는 것이
가장 많은 양을 충전할 수 있는지 계산하는 것이 핵심인 문제이다.

 

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

# 이동하는 방법
direction = [[0, 0], [-1, 0], [0, 1], [1, 0], [0, -1]]
P1 = list(map(int, input().split()))
p1x, p1y = 1, 1
P2 = list(map(int, input().split()))
p2x, p2y = 10, 10

먼저 이동하는 방법, 방향, 초기 좌표등을 설정해줬다.

 

    BC = []
    X, Y, C, POWER = 0, 1, 2, 3
    for i in range(A):
        BC.append(list(map(int, input().split())))

BC 리스트를 만들어 BC 데이터를 받고 인덱스를 접근할 때 구분하기 쉽게 하기 위해서
따로 구분하는 인자를 할당했다.

 

p1_charge = []
p2_charge = []

	for j in range(A):
		if abs(BC[j][Y] - p1y) + abs(BC[j][X] - p1x) <= BC[j][C]:
			p1_charge.append((BC[j][POWER], j))
		if abs(BC[j][Y] - p2y) + abs(BC[j][X] - p2x) <= BC[j][C]:
			p2_charge.append((BC[j][POWER], j))

BC의 범위 안에 있는지 확인하는 방법은 두 좌표의 차이를 절대값으로 더하는 것이다.
범위안에 있는 BC들을 리스트로 관리하였다. BC를 선택하는 작업에서 필요하기 때문이다.

 

중요한 부분은 이제 어떤 BC를 선택하는 것이 최대의 효율을 낼 수 있는지인데
두 사용자가 같은 BC를 선택하게되면 충전량을 반씩 사용한다.

혼자서 사용하는 것과 충전량의 차이가 없다. 
-> 각자 다른 BC를 선택할 수 있으면 그렇게 선택하는 것이 가장 많은 충전을 할 수 있는 방법이다.

 

	# 1번 사용자 먼저 선택하는 경우
    	temp1, used = 0, -1
        for P, idx in p1_charge:
            used = idx
            temp1 += P
            break
        for P, idx in p2_charge:
            if used != idx:
                temp1 += P
                break

	# 2번 사용자 먼저 선택하는 경우
        temp2, used = 0, -1
        for P, idx in p2_charge:
            used = idx
            temp2 += P
            break
        for P, idx in p1_charge:
            if used != idx:
                temp2 += P
                break

        answer += max(temp1, temp2)

1번 사용자가 먼저 선택하고 2번 사용자가 다른 번호를 선택하는 경우
2번 사용자가 먼저 선택하고 1번 사용자가 다른 번호를 선택하는 경우
2가지 경우로 나눠서 선택한 뒤 더 큰 값을 사용했다.

선택하는 순서에 따라서 더 많은 충전을 할 수 있지만 겹치는 경우가 발생하기 때문이다.

 

# 마지막엔 체크만하고 종료
        if i == M:
            break

        # 좌표 이동
        p1x += direction[P1[i]][1]
        p1y += direction[P1[i]][0]
        p2x += direction[P2[i]][1]
        p2y += direction[P2[i]][0]

0초에서 이동하기 전에 충전할 수 있는지 체크해야하기 때문에 반복문의 범위를 0 ~ M까지 수행하게 만들고
M번째에서는 좌표 이동 전에 break를 해서 반복을 종료시켰다.

이동 - 0 ~ M - 1
계산 - 0 ~ M

 

전체 코드

T = int(input())

for test_case in range(1, T+1):
    M, A = map(int, input().split())

    # 이동하는 방법
    direction = [[0, 0], [-1, 0], [0, 1], [1, 0], [0, -1]]
    P1 = list(map(int, input().split()))
    p1x, p1y = 1, 1
    P2 = list(map(int, input().split()))
    p2x, p2y = 10, 10

    BC = []
    X, Y, C, POWER = 0, 1, 2, 3
    for i in range(A):
        BC.append(list(map(int, input().split())))

    answer = 0
    for i in range(M+1):
        p1_charge = []
        p2_charge = []

        for j in range(A):
            if abs(BC[j][Y] - p1y) + abs(BC[j][X] - p1x) <= BC[j][C]:
                p1_charge.append((BC[j][POWER], j))
            if abs(BC[j][Y] - p2y) + abs(BC[j][X] - p2x) <= BC[j][C]:
                p2_charge.append((BC[j][POWER], j))

        p1_charge.sort(reverse=True)
        p2_charge.sort(reverse=True)

        temp1, used = 0, -1
        for P, idx in p1_charge:
            used = idx
            temp1 += P
            break
        for P, idx in p2_charge:
            if used != idx:
                temp1 += P
                break

        temp2, used = 0, -1
        for P, idx in p2_charge:
            used = idx
            temp2 += P
            break
        for P, idx in p1_charge:
            if used != idx:
                temp2 += P
                break

        answer += max(temp1, temp2)

        # 마지막엔 체크만하고 종료
        if i == M:
            break

        # 좌표 이동
        p1x += direction[P1[i]][1]
        p1y += direction[P1[i]][0]
        p2x += direction[P2[i]][1]
        p2y += direction[P2[i]][0]

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

어떤 BC를 선택하는지 계산하는 부분에서 조금 고민을 했었다.
문제를 자세히 읽어서 이해를 먼저 한 뒤 설계하고 풀이하는 습관을 가져야겠다.