반응형
문제
1756번: 피자 굽기
첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋
www.acmicpc.net
풀이
오븐의 지름이 위에서부터 5 6 4 3 6 2 3 이라고 하면 i >=2일때, i번째 오븐의 지름은 i-1번째 오븐보다 큰 게 의미가 없어집니다.
따라서 오븐의 지름 5 6 4 3 6 2 3은 5 5 4 3 3 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
44
45
|
#include<iostream>
#include<vector>
using namespace std;
int D, N;
int main()
{
vector<int> v;
cin >> D >> N;
for (int i = 0; i < D; i++)
{
int num;
cin >> num;
if (i != 0)
{
if (num > v[i - 1])
{
num = v[i - 1];
}
}
v.push_back(num);
}
int lastidx = v.size() - 1;
for (int i = 0; i < N; i++)
{
int dough;
cin >> dough;
if (lastidx < 0 || dough > v[0])
{
cout << 0;
return 0;
}
for (int j = lastidx; j >= 0; j--)
{
if (v[j] >= dough)
{
lastidx = j - 1;
break;
}
}
}
cout << lastidx + 2;
return 0;
}
|
cs |
|
|
|
이진 탐색
|
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
49
50
51
52
53
54
55
56
|
#include<iostream>
#include<vector>
using namespace std;
int D, N;
int main()
{
vector<int> v;
cin >> D >> N;
for (int i = 0; i < D; i++)
{
int num;
cin >> num;
if (i != 0)
{
if (num > v[i - 1])
{
num = v[i - 1];
}
}
v.push_back(num);
}
int start = 0;
int pos = 0;
int end = v.size() - 1;
for (int i = 0; i < N; i++)
{
int dough;
cin >> dough;
if (end < 0 || dough > v[0])
{
cout << 0;
return 0;
}
start = 0;
while (1)
{
if (start > end)
{
end = pos - 1;
break;
}
int mid = (start + end) / 2;
if (dough > v[mid])
end = mid - 1;
else
{
pos = mid;
start = mid + 1;
}
}
}
cout << pos + 1;
return 0;
}
|
cs |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 11507] 오르막 수 (C++) (0) | 2021.08.21 |
|---|---|
| [백준 17609] 회문 C++ (0) | 2021.08.21 |
| [백준 5557] 1학년 (C++) (0) | 2021.08.19 |
| [백준 2812] 크게 만들기 (C++) (0) | 2021.08.19 |
| [백준 16234] 인구 이동 (C++) (0) | 2021.08.18 |