문제 URL : www.acmicpc.net/problem/12931
12931번: 두 배 더하기
모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주
www.acmicpc.net
문제 접근법 : 사이즈 N인 A라는 배열의 원소가 전부 0일때 같은 사이즈인 N인 B라는 임의의 원소로 이루어진 배열을 만들라는 문제입니다. 두연산을 통해서
첫번째 :
- 배열에 있는 값 하나를 1 증가시킨다.
두번째 :
- 배열에 있는 모든 값을 두 배 시킨다
원소의 값은 0<=x<=1000 정수라는것이 보장이 되기때문에
첫번째 연산만 진행해도 A배열을 B라는 배열로 반드시 만들수있습니다.
그러나. 문제 조건은 연산을 최소화 시키는 문제이기에 배열에 잇는 모든값을 두배를 시키는것이
연산을 최소화 할수있는것이 지극히도 자명합니다.
또한 반대로 생각하면 A라는 배열을 B라는 배열로 만들수 있으니까 B라는배열을 A라는 배열로 만들수 있을겁니다.
물론 연산을 반대로 해야겠지요
첫번째 :
- 배열에 있는 값 하나를 1 감소시킨다.
두번째 :
- 배열에 있는 모든 값을 2배로 나눈다
이렇게해도 A-> B로 만들때나 B ->A로만들때 연산은 동일하게 나오겠죠?
최대한 연산을 최소하하기위해 모든값을 2배로 나누기위해 배열에 모든 값이 짝수라면 모든값을 2로 나누고 그렇지않으면 첫번째 연산을 진행하면 됩니다.
소스코드 :
|
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
32
33
34
35
36
37
38
39
40
41
42
43
|
//By 콩순이냉장고
#include <iostream> #include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<int> v;
int sum = 0;
void makehalf(){
for (int i = 0; i < v.size(); i++){
v[i] /= 2;
sum -= v[i];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++){
cin >> v[i];
sum += v[i];
}
int cnt = 0;
while (sum){
bool flag = true;//전부 2로 나눌수있는지
for (int i = 0; i < n; i++){
if (v[i] % 2){
flag = false;
v[i]--;
cnt++;
sum--;
}
}
if (flag){
makehalf();
cnt++;
}
}
cout << cnt << "\n";
}
|
cs |
궁금한점 혹은 모르는점이 있다면 언제든지 댓글은 환영입니다.
'백준' 카테고리의 다른 글
| 백준 16938 캠프 준비 (0) | 2020.12.31 |
|---|---|
| 백준 9944 NxM 보드 완주하기 (0) | 2020.12.31 |
| 백준 16953 A → B (2) | 2020.12.27 |
| 백준 1107 리모컨 (0) | 2020.11.29 |
| 백준 16562 친구비 (0) | 2020.10.02 |
