B1517

개요

백준 문제 1517번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : ?분
https://www.acmicpc.net/problem/1517

문제

버블소트의 스왑을 몇번 일어나는지 체크하라

코드

https://justicehui.github.io/ps/2019/04/23/BOJ1517/
예전 코드가 간단해서 참고하였던 기억이 난다.

풀이

문제 설명에서는 버블소트가 있어서 버블소트로 풀려고 할 수 있지만
시간초과를 보면 그럴 이유가 없음
따라서 분할 정복을 사용하게되면 곧 합병 정렬로 귀결됨
합병 정렬의 과정 중에서 버블정렬의 오른쪽보다 왼쪽 값이 크면 스왑이 발생하는데,
합병 정렬에서 conquer에서 왼쪽 값이 큰 경우 스왑 발생을 판단하면 되는 문제

배울 점, 메모

학부 2학년 알고리즘 과제에서 풀어보라고 하여 풀어본 문제여서 기억이 났다.
그때도 풀이를 보고 풀었던 기억이 난다.