자료구조&알고리즘/알고리즘 - 대회 알고리즘
-
[알고리즘 문제 풀이][유클리드] 백준 3036번 - 링자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 10. 2. 20:13
백준 3036번 링 문제입니다. (유클리드 호제법 = 최대공약수 구하는 방법) - 문제 설명: https://www.acmicpc.net/problem/3036 - 문제 풀이: 본 문제는 맨 왼쪽에, 첫번째로 있는 링이 돌 때 다른 링이 몇 바퀴 도는지를 출력하는 문제입니다. 문제에서 입력으로 주어지는 것은 각 링들의 반지름입니다. 만약에 반지름이 8, 2, 4 순이라면, 원의 둘레는 2πr 이므로, 16 π, 4 π, 8 π 가 됩니다. 그러면 두 원이 동시에 돌아갈 때 첫 번째 원이 1 바퀴 회전한다면 두번째 원이 4바퀴 회전할 것입니다. 이 문제에서 원하는 답은 첫번째 원 둘레 / 다른 원의 둘레가 될 것입니다. 이를 문제의 출력 형식인 기약 분수 형태로 출력한다면, 4/1, 2/1 이 될 것입니다..
-
[알고리즘 문제 풀이][좌표압축] 백준 13135번 - Corrupt Election자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 10. 1. 17:07
백준 13135번 Corrupt Election 문제입니다. (값/좌표 압축 학습용 문제) - 문제 설명: https://www.acmicpc.net/problem/13135 - 문제 풀이: 본 문제에서 가장 먼저 중요했던 것은, 문제에서는 무효표를 처리한 기준을 묻고 있지만 실제로 무효표 기준으로 따지게 되면 문제 풀이가 복잡하다는 것입니다. 무효표 기준이 "한 후보에게 X표 이상을 투표했거나 총 Y 표 이상 투표한 유권자들의 표를 무효표 처리한다." 이기 때문입니다. 본 문제의 풀이는 아래 출처의 해설을 참고하였습니다. 무효표 대신 유효표 기준으로 전환하게 되면 (무효표를 거르는 것과, 유효표를 선택하는 것은 결국 결과가 같습니다!), 한 후보에게 투표한 것이 무조건 X 아래이고, 총 투표도 무조건 ..