문제 링크입니다: https://www.acmicpc.net/problem/2262
2262번: 토너먼트 만들기
월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러도 랭킹이 높은 사람이 반드시 이기게 된다. 따라서 월드시에서는 게임을 흥미진진하게 만들기 위해서, 부전승을 여러 번 만들더라도 각 시합에 임하는 선수들의 랭킹 차이를 비슷하게 만들려고 한다. 토너먼트를 만들 때에는 이미 추첨이 된 순서대로 선수들을 배치하고, 왼쪽에서 오른쪽
www.acmicpc.net
그리디 알고리즘 혹은 DP 알고리즘을 통해 풀 수 있는 문제였습니다.
저는 우선 그리디 알고리즘으로 풀었고 DP로도 풀 예정입니다.
그리디하게 접근하자면 아래와 같습니다.
1. 랭킹이 제일 낮은 사람은 무조건 팀으로 묶이고 떨어지는 것이 유리합니다.
2. 랭킹이 제일 높은 사람은 마지막에 묶이지 않고 홀로 남습니다.
(수정: 2019.11.08 23:31)
DP로도 풀었습니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 12018번 Yonsei TOTO (0) | 2019.11.09 |
|---|---|
| 백준 1781번 컵라면 (2) | 2019.11.09 |
| 백준 1911번 흙길 보수하기 (0) | 2019.11.08 |
| 백준 2212번 센서 (0) | 2019.11.08 |
| 백준 1758번 알바생 강호 (0) | 2019.11.08 |