반응형
11509번: 풍선 맞추기
첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다.
www.acmicpc.net
방법 1. 배열 이용 -> 코드 짧음
방법 2. map 이용 -> 메모리 절약
입력한 값을 별도의 배열에 저장
이전에 입력된 값 목록에서 (현재 값+1)이 있는지 확인해야 함 -> 하나의 화살로 연속해서 터뜨림
단순하게 현재 입력한 값(1) 보다 더 큰 값(2)이 있는지만 확인하면
"2 1 1 1 1" 같은 반례 찾지 못함
현재 입력한 값(1) 보다 더 큰 값(2)이 “몇 개“ 있는지까지 확인해야 함
더 큰 값이 없으면 새로운 화살을 사용해야 하므로 cnt++
|
배열 사용: 코드 짧음 (메모리: 5924KB) 1.x 추가: arr[x]++; 2. x+1 확인 1) x+1 == 0: cnt++; 2) x+1 > 0: m[x+1]--; |
map 사용: 메모리 적게 사용 (메모리: 2152KB) 1.x 있음: m[x]++; x 없음: m.insert({x, 1}); 2. x+1 없음 or 0: cnt++; x+1 > 0: m[x+1]--; |
방법 1. 배열 이용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <iostream>
using namespace std;
int arr[1000001];
int main() {
int n, x, cnt = 0;
cin >> n;
while(n--) {
cin >> x;
arr[x]++;
arr[x + 1] == 0 ? cnt++ : arr[x + 1]--;
}
cout << cnt;
}
|
cs |
방법 2. map 이용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
#include <map>
using namespace std;
map<int, int> m;
int main() {
int n, x, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
if (m.find(x) == m.end())
m.insert({ x, 1 });
else
m[x]++;
if ((m.find(x + 1) == m.end()) || m[x + 1] == 0)
cnt++;
else
m[x + 1]--;
}
cout << cnt;
}
|
cs |
반응형