2024-01-21 PS 공부

한달만에 돌아왔네요! ㅠㅠ

사실 PS에 대한 흥미가 좀 떨어졌었는데, 입학하기 전까지 민트는 찍어야지(...) 하는 생각에 다시 문제를 풀게 되었습니다.

개인적으로 그리디를 어렵게 느끼고 있던 참이라서, 이번엔 백준 그리디 연습 문제집에 있는 문제들을 낮은 티어부터 쭉 돌아보았습니다.

 

 

11000: 강의실 배정(G5)

 

사용하는 최소 강의실의 개수는, 가장 많은 강의가 겹치는 시점에서의 강의 개수와 같다. 따라서 정렬을 통해 답을 O(NlogN)에 구할 수 있다.

 

 

2831: 댄스 파티(G4)

 

양수 남자 - 음수 여자, 혹은 음수 남자 - 양수 여자끼리만 짝지어 주어야 한다. 양수 남자와 음수 여자가 짝짓는 경우만을 생각해보자.

우선 키가 작은 순서대로 남자를 선택하면 최적해를 얻을 수 있다는 건 쉽게 알 수 있다. 그럼 임의의 남자에 대해, 가능한 키가 작은 여자와 춤을 추는 것이 최선이다. 가능한 키가 작은 여자가 아닌 다른 여자와 짝을 짓는 것이 최적해라고 한다면, 그 여자를 처음에 고른 여자로 바꿔치기해도 남여 쌍의 개수는 변하지 않기 때문이다.

따라서 양수 남자 - 음수 여자 쌍의 경우, 가능한 키가 작은 남자를 가능한 키가 작은 여자와 매칭시키는 것이 유리하다는 것을 이끌어낼 수 있다. 음수 남자 - 양수 여자 쌍은 반대로 생각하면 된다. 그렇게 정렬을 통해 O(NlogN)에 구현할 수 있다.

 

2138: 전구와 스위치(G5)

 

맨 앞 전구의 켜짐/꺼짐이 결정된다면 그 이후 어떤 전구를 눌러야 할 지는 결정된다. 따라서 두 상태에 대해서 가능한 값을 비교해 더 작은 값을 출력하면 된다.

 

 

9082: 지뢰찾기(G4)

 

앞 전구와 스위치(G5) 문제와 같은 맥락으로, 첫 번째 칸에 전구가 있는지/없는지에 따라 가능한 지뢰의 배치가 결정된다. 별해로, 한 칸의 지뢰는 2개 혹은 3개의 지뢰 정보(인접한 칸의 지뢰 개수)를 담고 있으므로, 지뢰 정보를 모두 더한 값을 3으로 나눠서 잘 처리하면 답이 된다!!)

 

 

2195: 문자열 복사(G5)

 

가능한 긴 부분문자열을 사용하는 것이 유리하다. 만약 그보다 짧은 부분문자열을 이용한 것이 최적해라고 했을 때, 이를 긴 부분문자열로 바꿔치기 했을 때 copy 함수의 사용횟수에는 전혀 손실이 일어나지 않는다. 따라서 O(N^2) 문자열 검색 느낌으로 해결할 수 있다.

 

 

1911: 흙길 보수하기(G5)

 

웅덩이에 대해 오름차순 정렬하고, 널빤지의 왼쪽 끝을 max(웅덩이의 왼쪽 끝, 지금까지 덮은 널빤지의 오른쪽 끝)으로 정하는 것을 반복하면 된다.