문제
강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.
일부 학생이 체육복을 도난 당했다.
여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 한다.
빌려줄 때 바로 앞번호나 뒷번호의 학생에게만 빌려줄 수 있다.
적절히 빌려주어 최대한 많은 학생이 체육 수업을 들을 수 있도록 하자.
전체 학생 수 : n
도난당한 학생들의 번호 : lost
여벌을 가진 학생들의 번호 : reserve
전체 학생 수는 2명 이상 30명 이하이다.
도난당한 학생은 1명 이상 n명 이하이고, 중복은 없다.
여벌을 가져온 학생은 1명 이상 n명 이하이고 중복은 없다.
여벌이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있다.
여벌이 있는 학생이 도난당한 경우, 한개만 도난 당했으며 남은 체육복이 하나이기 때문에 빌려줄 수 없다.
입출력 예시
| n | lost | reserve | return |
|---|---|---|---|
| 5 | [2,4] | [1,3,5] | 5 |
접근
탐욕법을 이용하여 풀 수 있다.
앞 번호부터 접근했을 때, 여벌을 가진 학생은 자신의 앞, 뒤 학생에게 체육복을 빌려줄 수 있는데,
이때 앞번호의 학생에게 우선적으로 빌려준다.
이럴 경우 항상 최적의 정답을 찾을 수 있다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, lost, reserve):
answer = 0
uni = [1] * (n+2)
for i in reserve:
uni[i] += 1
for i in lost:
uni[i] -= 1
for i in range(1, n+1):
if uni[i] == 2 and uni[i-1] == 0:
uni[i] = 1
uni[i-1] = 1
elif uni[i] == 2 and uni[i+1] == 0:
uni[i] = 1
uni[i+1] = 1
for i in range(1, n+1):
if uni[i] >= 1:
answer += 1
return answer
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> uni(n+2, 1);
for(int i = 0; i<reserve.size();i++){
uni[reserve[i]]++;
}
for(int i = 0; i<lost.size();i++){
uni[lost[i]]--;
}
for(int i = 1; i<=n;i++){
if(uni[i] == 2 && uni[i-1] == 0){
uni[i]--;
uni[i-1]++;
}
else if(uni[i] == 2 && uni[i+1]==0){
uni[i]--;
uni[i+1]++;
}
}
for(int i = 1; i<=n;i++){
if(uni[i] >= 1)
answer ++;
}
return answer;
}