728x90 greedy2 [그리디] 전구와 스위치(Python) 문제링크 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1. 핵심 좌우 상태 반전 그리디 유형 같은 곳을 2번 선택하면 선택하지 않는 것과 동일하므로 같은 곳을 2번 선택하지는 않는다. 순차적으로 진행하면서 눌러야하는 위치 판단하는게 유리 첫번째 위치가 선택되는지 안되는지 경우를 나누어서 생각 순차적으로 파악한 후에 마지막 원소가 동일한지 동일하지 않은지 판단한다. 마지막 원소가 같다면 잘 변경된 것이고 마지막 원.. 2024. 2. 18. [그리디] Greedy Algorithm / 자연수 M/2개의 쌍 문제링크 https://www.codetree.ai/missions/8/problems/m2-pairs-of-natural-numbers?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 합들 중 최댓값이 최소가 되도록 하려면 가장 작은 수와 가장 큰 수를 순서대로 매칭하면 된다. 방법1(메모리초과 + 시간초과) 각 값들을 max_heap, min_heap에 넣어서 m // 2만큼 max_q + min_q의 조합하고 조합한 것 중 최대값을 고른다. 문제는 m이 10억이므로 최.. 2024. 2. 16. 이전 1 다음 728x90 반응형