백준 1285번 동전 뒤집기

문제 링크입니다: https://www.acmicpc.net/problem/1285

1285번: 동전 뒤집기

 

얼핏 보면 시간 복잡도가 O(2^40)으로 보여 시간 안에 풀지 못할 문제처럼 보이는 문제였습니다.

하지만 다음과 같이 문제를 쪼개면 시간 내 풀 수 있는 문제입니다. (시간 복잡도: 400 * 2^20)

• 가능한 모든 조합에 대해 열을 직접 뒤집어 본다 (시간 복잡도: O(2^20))
• 열은 이미 뒤집혔고 행을 뒤집을 차례인데 행 내 뒷면 동전 개수를 파악하면 직접 뒤집을 필요가 없습니다. (시간 복잡도: O(20 * 20))
  • 앞면이 더 많으면 뒤집을 필요가 없고
  • 뒷면이 더 많으면 뒤집는다
  • 위 내용을 토대로 직접 뒤집지 않고 `sum += min(temp, N - temp)`로 대체 가능

 

 

개발환경:Visual Studio 2022

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

 

참고

인프런 10주완성-코딩테스트 - 큰돌 강사님