https://www.acmicpc.net/problem/18111
문제를 정리하면 땅 높이를 맞추어 주는 것인데 이제 땅을 쌓는건 1초, 깎는건 2초 걸리고 쌓을 때는 블록이 있어야 쌓을 수 있다.
최대높이가 256이기 때문에 땅을 0으로 고르는, 1로 고르는 ...... 256으로 고르는 시간을 각각 계산해서 비교해주는 식으로 풀었다.
위 방법을 brute force (브루트포스) 무차별 대입이라고 한다.
먼저 높이의 개수를 저장하는 hight 배열을 만들었다. 예를 들어
이런 땅이 있다면 hight[1] =2, hight[5]=2, hight[7]=5 이렇게 되는것이다.
이런식으로 저장하는 이유는 이 땅을 6으로 만들려고 한다면 6을 기준으로 작은 높이들은 쌓아올려주는데 이때의 블록 개수는 쌓아올리려는 쌓아올리려는 시작 높이와 목표 높이의 차 * 그 높이의 개수이다. 이때 쌓아올리려는 시작 높이는 목표 높이보다 작은 모든 높이로 계산해주면 된다. 그렇게 계산한 블록 수는 바로 목표 높이까지 쌓는 시간이 된다.
깎으려는 블록 수는 시작 높이와 목표 높이의 차 * 그 높이의 개수로 7로 예를 들면 (7-6)*5 이다.
그리고 깎는 시간은 블록 1개당 2초가 걸리기 때문에 2를 곱해주면 깎는데 걸리는 시간이 된다.
이렇게 해서 모든 높이들을 목표 높이와 비교해서 걸리는 시간을 구해준 후 마지막으로 깎은 블록과 원래 있던 블록 b를 더해서 쌓아올린 블록보다 작거나 같으면 가능한 땅 고르기이고 만약 쌓아올린 블록이 더 많다면 없는 블록을 쓴것이기 때문에 정답이 될 수 없는 값 이므로 비교대상에서 제외 시켜준다. 이렇게 목표 높이를 0부터 256까지 반복해주면 문제는 해결 된다. 답이 여러 개 있다면 땅 높이가 가장 높은 것을 답으로 하는데 우리는 for문으로 높이를 목표 높이를 0부터 256까지 순차적으로 가기 때문에 같은 시간이 걸리면 그 값을 그냥 저장해주면된다.
전체 코드
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
44
45
46
47
48
|
#include <iostream>
#include <string.h>
using namespace std;
int main(){
long long n, m, b;
int a;
cin >> n >> m >> b;
int hight[257];
memset(hight, 0, sizeof(hight));
for (int i = 0; i < n;i++){
for (int j = 0; j < m;j++){
cin >> a;
hight[a]++; // 높이의 개수 저장
}
}
long long ans = 999999999;
long long sum_block, sub_block;
long long time;
int ans2 = 0;
for (int i = 0; i < 257;i++){ //i는 만들 땅의 높이
sum_block = 0;
sub_block = 0;
for (int j = 0; j < i;j++){
sum_block += (i - j) * hight[j]; // 만들 땅의 높이 보다 작음 -> 쌓아올려야함 ->
//블록 수 = 만들 땅과의 높이 차 * 높이의 개수
}
for (int k = i + 1; k < 257;k++){ // 만들 땅의 높이 보다 높음
sub_block += (k - i) * hight[k];
//블록 수 = 만들 땅과의 높이 차 * 높이의 개수
}
if(sum_block<=sub_block+b){
//깎은 블록 + 원래 있던 블록이 많거나 같아야 블록을 쌓을 수 있음
time = sum_block + sub_block * 2;
if(ans >= time){ // 시간이 더 적게 걸리거나 같으면 값 저장
//0부터 256까지 점점 목표 높이를 높아서 검사하기 때문에 자동으로 높은 값 저장
ans = time; //걸리는 시간
ans2 = i; // 땅을 고른 높이
}
}
}
cout << ans << " " << ans2;
return 0;
}
|
cs |
사용 알고리즘 : 브루트 포스(brute force)
yea!
'알고리즘 > 백준' 카테고리의 다른 글
백준 1107 리모컨 c++ [컴공과고씨] (2) | 2022.03.27 |
---|---|
백준 3079 입국심사 c++ [컴공과고씨] (0) | 2022.03.26 |
백준 4375 1 c++ [컴공과고씨] (0) | 2022.03.24 |
백준 4963 섬의 개수 c++ [컴공과고씨] (0) | 2022.03.24 |
백준 2217 로프 c++ [컴공과고씨] (2) | 2022.03.24 |