#1489 대결
이번 문제는 Gold I 문제네요. A팀과 B팀이 n명의 사람들이 각각 1:1 대결해서 승패를 가리는데, 이기면 2점, 비기면 1점, 지면 0점을 받게 됩니다. 승부를 벌이는 두 사람의 능력치로 승패가 좌우되는데, 높은 능력치가 이기고, 능력치가 같으면 비기게 됩니다. 승부를 벌이는 두 팀의 n명의 능력치를 알고 있을 때, A팀이 얻을 수 있는 최대 점수를 계산하는 것이 목표입니다. 제가 생각한 방법은, 첫번째로 두 팀을 모두 정렬을 합니다. 두번째로 동적 계획법을 이용해서 A 팀이 얻을 수 있는 최대 점수를 구한다입니다. A 팀의 능력치를 오름차순으로 정렬했을 때, \( a_1, a_2, ..., a_n \)이라고 하고 B 팀 역시 \( b_1, b_2, ..., b_n \) 이라고 할 때, 다음과 같..
2022. 8. 19.
#1126 같은 탑(dynamic programming)
이 문제는 수열이 주어졌을 때, 각각의 수를 왼쪽, 오른쪽, 또는 사용치 않음으로 분류했을 때, 왼쪽 수열의 합과 오른쪽 수열의 합이 같은 경우, 그 값의 최대값이 얼마인가를 묻는 것입니다. 예를 들어서, 14 3 20 15 15 14 24 23 15 이란 값이 있다고 하죠. 그러면, 왼쪽에 [14] 오른쪽에 [14]란 수열이 있다면, 그 합이 14로 같기 때문에 같은 합이 될 수 있습니다. 하지만 이것은 최대값은 아닙니다. [14, 15]와 [14, 15]와 같이 쉽게 찾을 수 있는 값만 해도 29로 더 큰 값이 되기 때문이죠. [14, 20, 15, 15] 와 [3, 14, 24, 23] 로 나누면 64라는 최대값을 얻습니다. 여기서 중요한 것은 주어진 수열의 한 숫자는 왼쪽, 오른쪽, 또는 사용치않..
2020. 1. 4.
