[BOJ] 백준 14698번 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) c++

BOJ 문제 링크: https://www.acmicpc.net/problem/14698

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

슬라임이 각 에너지를 갖고 있고, 두 슬라임이 합쳐져서 생긴 슬라임이 갖는 에너지는 두 슬라임의 에너지 곱과 같다.

두 슬라임을 합치기 위해서는 각 슬라임이 갖고 있는 에너지의 곱만큼의 전기가 필요하다.

여러개의 슬라임이 주어졌을때 이 슬라임들을 하나의 슬라임으로 만들기 위한 전기의 최솟값을 구하는 문제이다.

 

직관적으로 에너지가 최소인 두 슬라임을 합쳐가기를 반복하는 그리디 알고리즘을 사용하면 답을 구할 수 있을거 같다.

priority_queue를 사용하면 이를 쉽게 구현할 수 있다.

참고로 원래 그리디 알고리즘을 사용할때는 정당성증명까지 신경쓰면서 문제를 풀어야 되지만,

이전에 알고스팟 문제로 풀었던 문자열 합치기랑 정당성증명 부분이 똑같은거 같아서 그냥 그리디 알고리즘을 사용했다.

MOD를 사용하는 부분에서 마지막에만 나머지를 취하는게 아니라 계산 도중 ret값에 나머지를 취하는걸 볼 수 있는데,

이렇게 하는 이유는 ret값이 longlong범위를 벗어나 오버플로우가 나는 것을 방지하기 위해서다.

이렇게 할수 있는 이유는 (A * B * C * D * . . . ) % MOD == (A * MOD) * (B * MOD) * (C * MOD) * (D * MOD) * . . . 의 원리와 같다.

 

사실 문제를 풀면서 계속 시간초과가 나와서 엄청 헤맸다. 처음에는 알고리즘 자체에 효율성이 떨어져서 시간초과가 나는줄 알고 한참 생각했다.

그러다 도저히 모르겠어서 일단 입출력을 cin, cout보다 빠른 scanf, printf를 바꿔서 제출했더니 정답이 나..왔더뻐..ㄱ

앞으론 scanf, printf를 더 애용해야겠다.

 

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314698.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!