Algorithm/Greedy

[Python] 1489 대결

턴태 2022. 6. 20. 11:21

📌 문제

팀 A와 B가 대결을 하려고 한다. 각 팀에 속한 사람은 다른 팀에 속한 사람과 대결을 해야 한다. 두 팀에 속한 각 사람은 대결을 한 번씩 해야 한다. 대결의 승자는 2점을 획득하고, 무승부인 경우에는 1점을 획득한다.

팀 A에 속한 사람의 능력치는 A1, A2, ..., AN이고, 팀 B에 속한 사람의 능력치는 B1, B2, ..., BN이다. 대결은 능력치가 높은 사람이 이기며, 능력치가 같은 경우 비긴다.

두 팀의 능력치가 주어졌을 때, 팀 A가 얻을 수 있는 점수의 최댓값을 구해보자.

📌 입력

첫째 줄에 팀에 속한 사람의 수 N이 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어지고, 셋째 줄에는 B1, B2, ..., BN이 주어진다.

📌 출력

첫째 줄에 팀 A가 얻을 수 있는 점수의 최댓값을 출력한다.

📌 제한

  • 1 ≤ N ≤ 50
  • 1 ≤ Ai, Bi ≤ 1,000

📌 문제 풀이

👨‍🏫 접근

가장 승점을 높게 받아야 한다. 문제에서 표독스러움이나 탐욕스러움이 느껴지면 그리디를 떠올리도록 하는 것도 좋다.

일단 어떻게 하면 가장 승점을 높게 받을 수 있는가? 1차원적으로 많이 이겨야 한다. 최대한 많이 이겨야 하며, 이기지 못하더라도 최소한 무승부로 끝나는 것이 좋을 것이다.

그렇다면 어떻게 해야 많이 이길 수 있을까? 그것은 항상 이길 수 있을 때 비등비등하게 이겨야 다음 순서에 영향을 덜 미친다. 즉, A 팀의 i번째 선수의 능력치보다 작은 값들 중에서 가장 큰 값을 고른다.

예를 들어,

3
10 5 1
10 5 1

이러한 입력이 주어졌을 때, 10의 능력치를 가진 사람이 1의 능력치를 가진 사람을 이긴다고 한다면, 그 다음 5의 능력치를 가진 사람은 5의 능력치를 가진 사람과 무승부를 가지며 총 승점은 3점에 그친다. 하지만, 10의 능력치를 가진 사람이 5의 능력치를 가진 사람을 이기고, 5의 능력치를 가진 사람이 1의 능력치를 가진 사람을 이긴다면 총 승점이 4점으로 3점보다 높다. 그렇기 때문에 매 승부에서 A 팀 선수의 능력치보다 낮은 능력치를 가진 선수들 중에서 가장 높은 k 값을 보유한 사람과 경쟁하는 것이 핵심이다.

👨‍🏫 문제 풀이

📄 전체 코드

N = int(input())

csort_a = [0 for i in range(1001)]
csort_b = [0 for i in range(1001)]

A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in A:
    csort_a[i] += 1
for i in B:
    csort_b[i] += 1

ans = 0

for i in range(1, 1001):
    while csort_a[i]:
        switch = False
        for j in range(i - 1, 0, -1):
            if csort_b[j]:
                switch = True
                ans += 2
                csort_a[i] -= 1
                csort_b[j] -= 1
                break
        if switch == False:
            break

for i in range(1, 1001):
    while csort_a[i] and csort_b[i]:
        ans += 1
        csort_a[i] -= 1
        csort_b[i] -= 1

print(ans)

📄 준비

N = int(input())

csort_a = [0 for i in range(1001)]
csort_b = [0 for i in range(1001)]

A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in A:
    csort_a[i] += 1
for i in B:
    csort_b[i] += 1

ans = 0

A팀과 B팀의 선수 능력치 상한이 1000까지 이므로 계수정렬을 사용할 수 있다.

그렇기 때문에 a와 b의 각각 카운팅을 저장할 수 있도록 리스트를 만든다. 이후 A팀과 B팀의 입력을 받아 카운팅을 저장한다.

📄 풀이

for i in range(1, 1001):
    while csort_a[i]:
        switch = False
        for j in range(i - 1, 0, -1):
            if csort_b[j]:
                switch = True
                ans += 2
                csort_a[i] -= 1
                csort_b[j] -= 1
                break
        if switch == False:
            break

for i in range(1, 1001):
    while csort_a[i] and csort_b[i]:
        ans += 1
        csort_a[i] -= 1
        csort_b[i] -= 1

print(ans)

1부터 1000까지 반복문을 돌면서 가장 큰 ans를 찾도록 한다.
카운팅 변수인 i에 해당하는 능력치를 가진 선수가 있다면 while 반복문으로 대결을 시작한다. i보다 작은 값 중에서 가장 큰 값을 찾기 위해서 for j in range(i - 1, 0, -1)로 for문을 작성하여 역순으로 탐색한다.

탐색에 성공하면 승리한 것이기 때문에 switch를 True로 바꾸어서 다시 반복문을 돌도록 하고 ans에 2를 더한다. 그리고 승부가 종료되었기에 csort_a[i]와 csort_b[j] 값을 1씩 감소시킨다.

한편 승리하지 못한 경우에는 무승부한 경우이기 때문에 다시 for문으로 1부터 1000까지 순회하면서 A팀과 B팀의 능력치가 같은 경우를 찾는다. 만약 그러한 값이 있으면 ans에 1을 더하고 둘의 값을 1씩 감소시킨다.

📌 총평

계수 정렬이 꽤 유용하게 쓰이는 것 같다. 그리고 문제를 풀기 전에 어떻게 하면 가장 큰 값을 유도할 수 있을까?를 코드로 작성하면서 사고하는 것이 아니라 직접적으로 어떻게 할 수 있을까? 생각을 먼저 하고 푸는 것도 좋은 방법인 것 같다. 의사코드처럼.

 

저작자표시 비영리