[BOJ] 랜덤 마라톤 (No. 29701, 10280, 28088, 16609, 9215, 12026, 1276)
by 구설구설29701
문제
모스 부호
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 1393 726 636 52.475%
문제
혜민이는 요즘 모스 부호에 관심이 많아졌다. 모스 부호는 짧은 신호와 긴 신호를 적절히 조합하여 문자 기호를 표기하는 방식이다. 각 문자를 나타내는 방식은 미리 정해져 있는데, 예를 들어, 짧은 신호를 '.', 긴 신호를 '-'로 나타낸다면, 모스 부호로 알파벳 'A'는 '.-', 숫자 1은 '.----'와 같이 표기할 수 있다. 모스 부호를 알고 있으면 위험한 상황에서 구조 요청을 하는 데 유용할 것 같아, 혜민이는 평상시에 친구들과 연락을 주고받을 때도 모스 부호를 사용하려고 한다. 혜민이는 친구들이 보내온 모스 부호를 올바르게 해독했는지 바로바로 확인하고 싶어졌다. 알파벳 A-Z, 숫자 0-9, 기호 ',', '.', '?', ':', '-', '@'로 이루어진 길이
N인 문자열을 변환한 모스 부호가 주어질 때, 주어진 모스 부호를 해독하여 원래의 문자열을 출력하는 프로그램을 작성해 보자.
각 문자를 모스 부호로 나타내는 방법은 아래 표에 정리되어 있다. (단, 표의 둘째, 넷째 열은 첫째, 셋째 열의 문자를 모스 부호로 변환한 결과를 나타내며, '.'는 짧은 신호를, '-'는 긴 신호를 의미한다.)
A .- B -...
C -.-. D -..
E . F ..-.
G --. H ....
I .. J .---
K -.- L .-..
M -- N -.
O --- P .--.
Q --.- R .-.
S ... T -
U ..- V ...-
W .-- X -..-
Y -.-- Z --..
1 .---- 2 ..---
3 ...-- 4 ....-
5 ..... 6 -....
7 --... 8 ---..
9 ----. 0 -----
, --..-- . .-.-.-
? ..--.. : ---...
- -....- @ .--.-.
입력
첫째 줄에 모스 부호로 변환하기 전 문자열의 길이를 나타내는 정수 N(1 <= N <= 100)이 주어진다.
둘째 줄에 원래의 문자열을 모스 부호로 변환한 메시지가 주어진다. 이 메시지에서 짧은 신호는 '.', 긴 신호는 '-'로 나타내며, 원래의 문자열을 구성하는 각각의 문자를 모스 부호로 변환한 결과는 공백으로 구분되어 있다.
위 표를 이용해 해독할 수 없는 메시지는 주어지지 않는다.
출력
주어진 모스 부호를 해독하여 길이 N인 문자열을 공백 없이 출력한다.
알파벳의 경우, 반드시 대문자로 출력한다.
예제 입력 1
5
.... . .-.. .-.. ---
예제 출력 1
HELLO풀이
모스부호를 map에 집어넣은 뒤 각 입력 별로 찾아서 합친 뒤 정답을 출력하면 되는 문제이다.
질문 게시판에 map에 넣는 코드는 있길래 그대로 썼다.
#include <bits/stdc++.h>
using namespace std;
string ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
map<string, char> m;
m.insert({".-", 'A'});
m.insert({"-...", 'B'});
m.insert({"-.-.", 'C'});
m.insert({"-..", 'D'});
m.insert({".", 'E'});
m.insert({"..-.", 'F'});
m.insert({"--.", 'G'});
m.insert({"....", 'H'});
m.insert({"..", 'I'});
m.insert({".---", 'J'});
m.insert({"-.-", 'K'});
m.insert({".-..", 'L'});
m.insert({"--", 'M'});
m.insert({"-.", 'N'});
m.insert({"---", 'O'});
m.insert({".--.", 'P'});
m.insert({"--.-", 'Q'});
m.insert({".-.", 'R'});
m.insert({"...", 'S'});
m.insert({"-", 'T'});
m.insert({"..-", 'U'});
m.insert({"...-", 'V'});
m.insert({".--", 'W'});
m.insert({"-..-", 'X'});
m.insert({"-.--", 'Y'});
m.insert({"--..", 'Z'});
m.insert({".----", '1'});
m.insert({"..---", '2'});
m.insert({"...--", '3'});
m.insert({"....-", '4'});
m.insert({".....", '5'});
m.insert({"-....", '6'});
m.insert({"--...", '7'});
m.insert({"---..", '8'});
m.insert({"----.", '9'});
m.insert({"-----", '0'});
m.insert({"--..--", ','});
m.insert({".-.-.-", '.'});
m.insert({"..--..", '?'});
m.insert({"---...", ':'});
m.insert({"-....-", '-'});
m.insert({".--.-.", '@'});
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
ans += m[s];
}
cout << ans << '\n';
return 0;
}
10280
문제
Pizza voting
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
3 초 256 MB 344 153 106 44.915%
문제
당신은 팀원인 Alice와 Bob과 함께 프로그래밍 대회를 준비하고 있다. 몇 시간 동안 열심히 훈련한 후 휴식을 취하며 피자를 먹기로 했다. 세 사람이 함께 큰 피자를 주문하려고 한다. 하지만 어떤 종류의 피자를 먹을지 결정해야 한다.
당신은 좋아하는 피자 종류를 알고 있다. 하지만 Alice와 Bob은 각자 다른 조건을 가지고 있다. Alice는 다이어트 중이라 가능한 칼로리가 적은 피자를 원한다. 반면 Bob은 Alice를 괴롭히기 위해 가능한 칼로리가 많은 피자를 원한다.
당신은 투표를 통해 피자를 선택하기로 했다. 그러나 한 종류의 피자를 뽑는 방식으로는 결론이 나지 않을 것이므로, 거부권(veto voting) 방식을 사용하기로 했다. 세 사람은 번갈아가며 피자를 거부하는 방식이다. 먼저 Alice가 한 종류의 피자를 거부하고, 그 다음은 Bob이 거부, 마지막으로 당신이 거부할 차례다. 이후에는 다시 Alice의 차례로 돌아가며, 이런 방식으로 피자가 한 종류만 남을 때까지 진행된다.
주의:
Alice는 항상 칼로리가 가장 많은 피자를 거부한다.
Bob은 항상 칼로리가 가장 적은 피자를 거부한다.
당신은 당신이 좋아하는 피자가 남을 수 있도록 전략적으로 행동한다.
입력의 첫 줄에는 피자의 수
𝑛(1 ≤ 𝑛 ≤ 100,000)과 당신이 좋아하는 피자의 인덱스 𝑝(1 ≤ 𝑝 ≤ 𝑛)이 주어진다.
(인덱스는 1부터 시작한다.)
출력
한 줄에 출력한다. 만약 당신이 좋아하는 피자가 남도록 투표를 할 수 있다면 "YES"를 출력한다. 그렇지 않으면 "NO"를 출력한다.
예제 입력 1
5 2
500 Margherita
600 Salami
700 Hawai
800 Speciale
900 Doener
예제 출력 1
YES
예제 입력 2
5 4
500 Margherita
600 Salami
700 Hawai
800 Speciale
900 Doener
예제 출력 2
NO풀이
굳이 각 피자의 정보를 입력 받을 필요도 없는 문제이다.
alice, bob, 나 세명이 각자 거부해야 하는 횟수를 구한 뒤 alice와 bob이 거부하는 피자에 내가 원하는 인덱스가 포함되어 있는지 여부만 확인하면 된다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int alice, bob, me;
vector<pair<int, string>> pizza;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
alice = bob = me = n / 3;
if (n % 3 == 0) {
me--;
} else if (n % 3 == 2) {
alice++;
}
if (n - m >= alice && m > bob) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
28088
문제
응애(EASY)
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 1024 MB 558 250 175 51.020%
문제
이 문제는
N,M,K의 제한 범위만 제외하고 28089번 응애(HARD)와 같은 문제이다.
SCSC 동아리원들은 모두 응애이다. 응애들은 응애를 볼 때 응애!라고 인사를 한다.
한 사람이 응애!라고 인사를 하면 그 양 옆에 있는 친구도 응애!라고 인사를 해야 한다. 다만, 양 옆에서 동시에 응애!라는 인사를 받으면 너무 응애가 된 나머지 인사를 하는 것을 잊어버려 인사를 하지 못한다.
N명의 SCSC 동아리원이 원 모양으로 둥글게 서 있고 그 중 M명의 부원이 처음에 응애!라고 인사를 할 때 K번 인사를 진행한 후, 다음에 인사할 사람의 수를 구하여라.
인사는 모두가 동시에 하며, 동아리원들은 시계 방향으로 0번부터 N - 1번까지 순서대로 서 있다고 가정한다.
입력
첫째 줄에 N,M,K가 공백으로 구분되어 주어진다. (3 <= N <= 200; 1 <= M <= N; 0 <= K <= 10^6)
둘째 줄부터 M개의 줄에 걸쳐 처음에 인사할 사람의 번호가 한 줄에 하나씩 주어진다. 같은 입력이 2번 이상 주어지지 않는다.
출력
K번 인사를 진행한 후, 다음에 인사할 사람의 수를 출력한다.
예제 입력 1
5 3 2
3
0
4
예제 출력 1
2
예제 입력 2
4 1 3
3
예제 출력 2
0
예제 입력 3
4 4 0
0
1
2
3
예제 출력 3
4
처음에 인사할 사람이 4명이므로 답은 4이다.풀이
원래는 초기 상태를 기록한 다음에 k번 반복하면서 각 상태를 업데이트 하는 방식으로 구현했는데, 시간 초과가 발생하였다.
그래서 상태 변화가 없는데도 무의미한 루프를 반복하는 지 확인하고, 모듈러 연산을 항상 수행하는 것이 문제가 되나 싶어서 0 또는 n-1인덱스일 때만 하도록 수정해서 해결완료.
문제와는 별개로 28089 문제가 궁금해서 풀이를 봤는데, 선형변환을 사용해야 하는 문제인걸 보고 백준에서 선형 변환이 사용되는 문제가 있을 수 있구나 라는 것을 알게 되었다. 대박쓰
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long n, m, k, ans = 0;
cin >> n >> m >> k;
vector<bool> hi(n, false);
for (int i = 0; i < m; i++) {
long long temp;
cin >> temp;
hi[temp] = true;
}
for (int t = 0; t < k; t++) {
bool changed = false;
vector<bool> temp = hi;
for (int j = 0; j < n; j++) {
bool left, right;
if (j == 0) {
left = hi[(j - 1 + n) % n];
right = hi[j + 1];
} else if (j == n - 1) {
left = hi[j - 1];
right = hi[0];
} else {
left = hi[j - 1];
right = hi[j + 1];
}
if (left == right) {
temp[j] = false;
} else {
temp[j] = true;
}
if (temp[j] != hi[j]) {
changed = true;
}
}
hi = temp;
if (!changed) {
break;
}
}
for (int i = 0; i < n; i++) {
if (hi[i]) {
ans++;
}
}
cout << ans << '\n';
return 0;
}
16609
문제
Inflation
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 295 190 97 72.932%
문제
NWERC 2018 대회에서 주최측은 특별한 풍선을 준비했다. 모든 풍선을 동일한 크기로 준비하는 대신, 크기가 1부터 n까지의 정수인 풍선을 각각 하나씩 구매했다. 크기가 s인 풍선은 s 데시리터의 용량을 가진다.
풍선을 손으로 불지 않기 위해, 주최측은 n개의 헬륨 가스 캔스터도 구매했다. 각 캔스터는 한 개의 풍선을 부풀리기 위해서만 사용할 수 있으며, 반드시 완전히 비워야 한다(캔스터를 풍선에서 분리하기 전에 가스를 남겨두는 것은 불가능하다).
하지만 헬륨 캔스터는 중고 판매장에서 구매했기 때문에, 각 캔스터에 들어 있는 헬륨의 양이 다를 수 있다. 일부 캔스터는 비어 있을 수도 있다! 이런 어려운 상황에서, 캔스터와 풍선을 최적의 방식으로 배치해야 한다.
주최측은 모든 가스 캔스터를 각각 다른 풍선에 할당하되, 가장 적게 채워진 풍선이 여전히 최대한 높은 비율로 채워지도록 하고 싶어 한다. 이 때, 모든 풍선이 자신의 용량 이상으로 부풀려지면 폭발한다. 폭발은 문제가 되므로 반드시 피해야 한다.
모든 풍선을 폭발 없이 부풀릴 수 있다면, 모든 풍선이 최소한 f의 비율만큼 채워질 수 있는 최대 비율 f 를 출력해야 한다. 불가능한 경우, “impossible”을 출력한다.
입력
입력은 다음과 같이 구성된다:
1. 첫 번째 줄에는 정수 n (1 <= n <= 2 * 10^5)이 주어진다. 이는 풍선과 가스 캔스터의 개수를 의미한다.
2. 두 번째 줄에는 n개의 정수 c_1, c_2, ... , c_n (0 <= c_i <= n)가 주어진다. 이는 각각의 가스 캔스터에 들어 있는 헬륨의 양(데시리터 단위)을 나타낸다.
출력
모든 풍선을 폭발 없이 부풀릴 수 있다면, 최소한의 비율 f를 최대화한 값을 출력한다.
모든 풍선을 부풀릴 수 없다면, “impossible”을 출력한다.
출력 값은 절대 오차 또는 상대 오차가 10^{-6} 이내여야 한다.풀이
각 캔스터의 정보를 벡터에 저장한 다음 벡터를 오름차순으로 정렬하여 풍선이 작은 순으로 배정해야 한다.
그렇게 해야지 가장 f가 최대화 되기 때문이다.
각 계산한 비율이 1보다 크다면 거기서 impossible을 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
double minimum = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<double> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
if (v[i] / (i + 1) > 1) {
cout << "impossible\n";
return 0;
}
if (v[i] / (i + 1) < minimum) {
minimum = v[i] / (i + 1);
}
}
cout.precision(10);
cout << minimum << '\n';
}
9215
문제
\[\frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1d_2 + n_2d_1}{d_1d_2}\]
신나는 분수 계산
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 297 119 99 51.295%
문제
유리수는 두 정수의 비로 나타낼 수 있다. 분자(n)와 분모(d)가 주어지면 이 분수를 n/d으로 쓴다. 유리수의 표현 방법은 유일하지 않다. 예를 들어, 1/2과 2/4는 그 값이 같다. 어떤 유리수 표현법 n/d이 gcd(|n|, |d|) = 1이라면 이것이 "기약분수로 표현되었다"라고 한다. 따라서 1/2은 기약분수로 표현되었지만 2/4는 아니다.
유리수의 덧셈은 다음과 같이 정의된다. 오른쪽 항이 기약분수로 표현되어 있다는 보장은 없음에 주목하라.
분자가 분모보다 크거나 같은 유리수는 대분수 꼴로 표현할 수 있는데, 이것은 정수부와 소수부로 이루어 진다. 예를 들어,
3,1/3은 16/3과 같은 값을 가지는 대분수 표현이다.
당신이 할 일은 유리수열을 읽어 그 합을 출력하는 것이다.
입력
입력은 몇 개의 테스트로 구성된다. 각 테스트의 정보는 첫 줄에 n(1 ≤ n < 1000)을 포함한다. n = 0인 경우 입력이 끝난다.
다음 n개의 줄은 공백이 없는 하나의 문자열이다. 각 문자열은 유리수 하나를 나타내며, 다음 세 형태 중 하나이고 기약분수로 표현되지 않을 수 있다 (w, n과 d는 정수이다: 0 ≤ w,n < 1000, 1 ≤ d < 1000).
w,n/d: (w * d + n) / d와 값이 같은 대분수
n/d: 정수부가 0인 유리수
w: 소수부가 0인 정수
출력
출력은 화면에 나온 대로 테스트 번호를 포함하여 합을 기약분수로 표현하여 출력한다. 만약 합의 정수부나 소수부가 없다면 각 부분을 생략하여 출력한다. 특수한 경우로, 정수부와 소수부가 모두 없다면 0을 출력해야 한다.
예제 입력 1
2
1/2
1/3
3
1/3
2/6
3/9
3
1
2/3
4,5/6
0
예제 출력 1
Test 1: 5/6
Test 2: 1
Test 3: 6,1/2풀이
입력받은 분수들을 ~,~, ~/~의 여부를 확인하면서 백터에 파싱해 집어 넣고,
하나 씩 더하면서 ~gcd~를 이용해 기약분수 꼴로 바꿔주면 된다.
출력할 때도 ~,~, ~/~의 여부에 따라서 달라지기에 입출력 형식이 살짝 까다로웠다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, t = 0;
while (cin >> n) {
if (n == 0) break;
vector<pair<long long, long long>> v(n, {0, 1});
long long ansint = 0, ansnum = 0, ansden = 1;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
if (s.find(',') != string::npos) {
ansint += stoi(s.substr(0, s.find(',')));
s = s.substr(s.find(',') + 1);
}
if (s.find('/') == string::npos) {
ansint += stoi(s);
} else {
v[i].first = stoi(s.substr(0, s.find('/')));
v[i].second = stoi(s.substr(s.find('/') + 1));
}
}
for (int i = 0; i < n; i++) {
ansnum = ansnum * v[i].second + ansden * v[i].first;
ansden *= v[i].second;
long long g = gcd(abs(ansnum), ansden);
ansnum /= g;
ansden /= g;
}
ansint += ansnum / ansden;
ansnum %= ansden;
cout << "Test " << ++t << ": ";
if (!ansint && !ansnum) cout << 0;
if (ansint) cout << ansint;
if (ansint && ansnum) cout << ',';
if (ansnum) cout << ansnum << '/' << ansden;
cout << '\n';
}
return 0;
}
12026
문제
BOJ 거리
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 3812 2295 1911 62.025%
문제
BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다.
스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.
BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다.
스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다.
스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O, J, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.
스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 1 ≤ N ≤ 1,000이 주어진다.
둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.
출력
스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.
예제 입력 1
9
BOJBOJBOJ
예제 출력 1
8
예제 입력 2
9
BOJBOJBOJ
예제 출력 2
8
예제 입력 3
8
BJJOOOBB
예제 출력 3
-1
예제 입력 4
13
BJBBJOOOJJJJB
예제 출력 4
50
예제 입력 5
2
BO
예제 출력 5
1
예제 입력 6
15
BJBOJOJOOJOBOOO
예제 출력 6
52풀이
dp라는 것은 문제를 읽고 알아챘는데, 그래서 어떻게 접근해야 하는지 생각하는데 시간이 걸렸다.
시작 지점인 dp[1] = 0으로 설정하고 이중 for문을 사용해서 가능한 모든 경우를 계산하더라도 시간 복잡도에서 문제가 발생하지 않는다.
이후에 dp[n]이 초기값이면 도착할 수 없는 것이기에 -1을, 그렇지 않다면 dp[
더 빠르게 풀 수 있는지는 몰라용
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
string s;
cin >> n >> s;
vector<int> dp(n + 1, INT32_MAX);
dp[1] = 0;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if ((s[j - 1] == 'B' && s[i - 1] == 'O') ||
(s[j - 1] == 'O' && s[i - 1] == 'J') ||
(s[j - 1] == 'J' && s[i - 1] == 'B')) {
if (dp[j] != INT_MAX) {
dp[i] = min(dp[i], dp[j] + (i - j) * (i - j));
}
}
}
}
if (dp[n] == INT_MAX) {
cout << -1 << '\n';
} else {
cout << dp[n] << '\n';
}
}
1276
문제
PLATFORME
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 778 330 281 44.888%
문제
새로운 플랫폼 게임의 레벨을 설계 중이다. 플랫폼의 위치는 이미 정해졌다. 일반적인 의견과 달리, 플랫폼은 공중에 떠 있을 수 없고, 반드시 기둥으로 지지되어야 한다. 정확히 말하자면, 플랫폼의 양쪽 끝은 각각 바닥이나 다른 플랫폼 위에 있는 기둥으로 지지되어야 한다.
좌표계에서 플랫폼의 위치가 주어진다. 각 플랫폼의 위치는 수직 거리(고도, altitude)와 수평 방향의 시작 및 끝 좌표로 결정된다. 각 지지 기둥은 플랫폼 끝에서 0.5 단위 떨어진 위치에 세워진다.
모든 플랫폼을 지지하기 위해 필요한 기둥의 총 길이를 구하라.
입력
첫 번째 줄에는 정수 N이 주어진다. N은 플랫폼의 개수이며, 1 이상 100 이하이다.
다음 N개의 줄에는 각각 하나의 플랫폼 위치가 주어진다. 각 줄은 세 개의 정수 Y, X1, X2로 이루어져 있다.
Y는 플랫폼의 고도(altitude)를 나타낸다.
X1과 X2는 플랫폼의 수평 방향 시작 및 끝 좌표를 나타낸다.
X2 > X1 + 1 (즉, 모든 플랫폼의 길이는 최소 2 이상이다).
모든 좌표는 양의 정수이며, 10000보다 작다.
플랫폼은 서로 겹치지 않는다.
출력
모든 플랫폼을 지지하기 위해 필요한 기둥의 총 길이를 출력한다.
예제 입력 1
3
1 5 10
3 1 5
5 3 7
예제 출력 1
14
예제 입력 2
5
50 50 90
40 40 80
30 30 70
20 20 60
10 10 50
예제 출력 2
200풀이
플랫폼들을 오름차 순으로 정리하고,
플랫폼의 다리가 이전의 다리들의 사이에 위치 한다면 이전 다리의 높이를 고려하여 더해야 하는 다리의 길이를 계산하는 방식으로 풀었다.
다리의 기준이 뭔가 좀 그랬던 문제.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> platform;
int ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
platform.resize(n);
for (int i = 0; i < n; i++) {
int y, x1, x2;
cin >> y >> x1 >> x2;
platform[i] = {y, x1, x2};
}
sort(platform.begin(), platform.end());
for (int i = 0; i < n; i++) {
int y = platform[i][0], x1 = platform[i][1], x2 = platform[i][2];
int left_support = y, right_support = y;
for (int j = i - 1; j >= 0; j--) {
int ny = platform[j][0], nx1 = platform[j][1], nx2 = platform[j][2];
if (x1 + 0.5 > nx1 && nx2 > x1 + 0.5) {
left_support = min(left_support, y - ny);
}
if (x2 - 0.5 > nx1 && nx2 > x2 - 0.5) {
right_support = min(right_support, y - ny);
}
}
ans += left_support + right_support;
}
cout << ans << '\n';
return 0;
}'Algorithm > BOJ' 카테고리의 다른 글
블로그의 정보
공부중임
구설구설