https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1. Preview 시간 복잡도: O(N) 공간 복잡도: O(N) 참고 : https://velog.io/@waoderboy/BOJ-%EB%B0%B1%EC%A4%80-2138-%EC%A0%84%EA%B5%AC%EC%99%80-%EC%8A%A4%EC%9C%84%EC%B9%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC 유형: 그리디 2. 초기 접근 방법 중앙점이 ..

[초기 접근 방법] 1) 구현 박스와 크레인을 내림차순 정렬을 한다. 무거운 박스부터 무거운 크레인을 배정한다. 배정을 못할 시, 크레인 순환을 +1 한다. → 무거운 박스는 옮기지 못하지만 작은 박스는 옮길 수 있음 2) 이분 탐색 현재 박스 무게에 맞는 크레인을 이분 탐색으로 배정한다. 이 때 박스 무게 초과인 upper_bound가 아닌 이상인 lower_bound로 탐색을 해야 한다. 모든 박스를 효율적으로 이동하기 위해, 무거운 박스부터 크레인으로 옮긴다. → ? [생각] 이분 탐색으로 풀리지 않자 검색하여 코드를 참고했다. 그리디로 푸는 것..😂 그리디 문제인지 알고 접근하면, 바로 그리디적으로 생각하게 되는데 유형을 모르고 푸니 완전탐색, 백트래킹, 이분탐색, dp 여러 측면에서 생각하게 되..