2020-09-05
초급 : 17262 팬덤이 넘쳐흘러 (Bronze I)
17262번: 팬덤이 넘쳐흘러
선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬�
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int N;
int ef = 100001, sl = -1;
int main() {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
cin >> N;
for (int i = 1; i <= N; ++i) {
int s, e; cin >> s >> e;
if (s > sl) sl = s;
if (e < ef) ef = e;
}
cout << max(0, sl - ef);
return 0;
}
가장 먼저 떠나는 사람이 떠나는 시간 ~ 가장 늦게 도착한 사람이 도착한 시간 이 얼마나 되는지 구하면 된다.
인사를 하는데 소요되는 시간이 0이라고 하니 0만큼만 머물러도 된다.
중급 : 16193 차이를 최대로 2 (Gold III)
16193번: 차이를 최대로 2
첫째 줄에 N (3 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100,000보다 크거나 같고, 100,000보다 작거나 같다.
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll res;
vector<int> v;
deque<int> d;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N; cin >> N;
v.resize(N);
for (int i = 0; i < N; ++i) {
cin >> v[i];
}
sort(v.begin(), v.end());
for (int i : v) d.push_back(i);
ll M = d.back(), m = d.front();
res += M - m;
d.pop_back(); d.pop_front();
while (d.size() >= 2) {
res += abs(M - d.front());
res += abs(m - d.back());
m = d.front();
M = d.back();
d.pop_front();
d.pop_back();
}
if (!d.empty()) {
res += max(abs(M - d.front()), abs(m - d.front()));
}
cout << res;
return 0;
}
배열을 크기 내림차순으로 정렬했을 때 각 원소를 1, 2, 3, ..., N-1, N 번째라 하자.
위와 같이 양 옆에 하나씩 붙여나가면 차이를 최대로 만들 수 있다.
단, 배열의 크기가 홀수라 마지막에 하나가 남는 경우 한 가지 조심할 것이 있다.
10 8 1 을 예로 들면,
위의 규칙대로 8을 추가한다면 10 왼쪽에 오게 되지만 1 오른쪽에 오면 차이가 더 커진다.
따라서 배열의 크기가 홀수일 때 마지막 남는 원소의 위치만 따로 처리해주면 된다.
실제로 덱에 넣을 필요는 없고 그때그때 차이를 계산해주면 좋다.
고급 : 2505 두 번 뒤집기 (Platinum V)
2505번: 두 번 뒤집기
첫줄에는 숫자판의 크기를 나타내는 정수 N (5≤N≤10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다.
www.acmicpc.net
from sys import stdin
def input(): return stdin.readline().rstrip()
N = int(input())
O = list(map(int, input().split()))
flip = 0
res = []
s = [x for x in O]
for i in range(N):
if flip == 2: break
if s[i] != i+1:
e = s.index(i+1)
s[i:e+1] = s[i:e+1][::-1]
flip += 1
res.append((i+1,e+1))
if not all([x == i+1 for i, x in enumerate(s)]):
flip = 0; res.clear()
s = [x for x in O]
for i in range(N-1,-1,-1):
if flip == 2: break
if s[i] != i+1:
e = s.index(i+1)
s[e:i+1] = s[e:i+1][::-1]
flip += 1
res.append((e+1,i+1))
for i in res: print(i[0],i[1])
for i in range(2-len(res)): print("1 1")
맨 앞부터 확인하면서, 처음 놀이판과 다른 수(6)가 발견되면 그 수(1)의 위치까지 뒤집는다.
똑같이 차례대로 진행하다가 같은 조건에서 같은 행위를 한 번 더 하면 원래 놀이판을 구할 수 있다.
단 예외가 두 가지 있다.
첫 예외로, 5 4 3 을 뒤집히면 한 번의 뒤집기만으로 처음 놀이판을 만들 수 있다.
문제에서 반드시 두 번 뒤집으라고 했으므로 구간 [1:1]을 뒤집는 등 의미 없는 행위를 한 번 해주면 된다.
시작부터 처음 놀이판이 완성되어 있을 수도 있는데, 이 역시 구간 [1:1] 뒤집기를 두 번 하면 된다.
둘째 예외로, 이렇게 해서 답이 안 나올 수 있다.
이걸 위 방식 그대로 따라 하면
이렇게 된다.
물론 한 번 더 뒤집어서 처음 놀이판을 만들 수 있겠지만 이 문제에서는 두 번만 뒤집어야 한다.
이런 경우엔 뒤에서부터 탐색하면 답이 나온다.
맞왜틀~ 거리다가 위 반례를 찾고 나서야 풀 수 있었다.
댓글