개요
6주차 스터디는 정렬 관련 6문제였다.
A번
문제 요약
묘목을 심는데 1일, 자라는데 T_i일이 걸린다.
묘목을 모두 심어서 다 자라게 하는 최소 일수 구하기
설명
정렬해서 오래 걸리는 것부터 심으면 된다.
B번
문제 요약
일직선 위에 집들의 위치가 주어질 때, 안테나를 설치해 집들과의 거리의 총합을 최소화하려면
안테나를 어디 설치해야 하는지 구하는 문제
설명
안테나가 어떤 집보다 오른쪽에 있다면, 오른쪽으로 갈때마다 그 집과의 비용이 1씩 증가한다. 왼쪽도 마찬가지.
그래서 좌우에 있는 집의 수를 같게 해 주면 된다.
이해가 잘 안 간다면, 아래와 같이 생각하면 된다.
- 왼쪽 집의 수를 L이라 하고, 오른쪽 집의 수를 R이라 하자.
- L < R이라면 무조건 오른쪽으로 옮기는게 이득이다. (1칸 오른쪽으로 옮길 때마다 왼쪽 집들의 비용은 L만큼 증가, 오른쪽 집들의 비용은 R만큼 감소)
- 그 반대도 같으므로, L == R인 어느 지점이 최소라고 할 수 있다. (집의 개수가 홀수라면 1 차이가 나는데 상관 없다.)
따라서 중간값을 구해서 출력하면 끝이다.
C번
문제 요약
그냥 구현 문제
설명
많이 귀찮은 구현 문제다. 설명 생략
D번
문제 요약
고속도로 위에 N개의 센서가 있는데, 집중국과 통신이 가능해야 한다. 집중국은 최대 K개 설치가 가능하다.
집중국의 통신 가능 영역은 구간으로 표현된다. 구간 길이의 총합을 최소화하는 문제다.
다르게 설명하면, K개의 구간으로 N개의 점을 덮으면서 구간의 길이를 최소화하는 문제다.
설명
점들 간의 모든 구간(N-1개)을 구한다. 그 뒤 정렬해 가장 큰 K-1개의 구간들을 없애면 끝이다.
E번
문제 요약
크레인들과 짐들이 있다. 크레인은 매 초 하나의 짐을 옮길 수 있다.
짐들의 무게와, 크레인마다의 옮길 수 있는 최대 무게가 주어질 때
짐을 다 옮길 수 있는 최소 시간을 구하는 문제
설명
그리디하게, 매 초 가장 센 크레인부터 각각 실을 수 있는 가장 무거운 상자를 실으면 된다.
가장 무거운 상자를 고르는 것은 multiset에서 lower bound로 찾았다.
F번
문제 요약
음이 아닌 수들의 수열이 주어졌을 때, 배열해서 만들 수 있는 가장 큰 수를 출력하기
설명
정렬 기준을 어떻게 잘 만들면 되지 않을까 하는 아이디어를 떠올릴 수 있을 것이다.
가장 먼저 생각해볼 만한 접근은 가장 높은 자릿수부터 비교하는 것이다.
그런데 이렇게 했을 때는 자릿수가 다를 때 문제가 생긴다.
예를 들어, [1, 10, 102]에서는 1 102 10이고, [1, 10, 100]일 때는 1 10 100이다.
그래서 자릿수를 근본적으로 다르지 않게 하는 것이 해결책이다.
따라서 약간의 그리디한 아이디어로, int(str(A)+str(B)) > int(str(B)+str(A))라면 A를 앞으로 보내는 방법으로 정렬하면 된다. (자릿수가 다를 수가 없다.)
꽤 참신하고 재밌는 문제였다.