[BOJ] 랜덤 마라톤 (No. 9086, 30589, 15719, 15803, 24315, 11366, 12933, 12842)
by 구설구설9086
문제
문자열
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 90095 57137 51660 64.153%
문제
문자열을 입력으로 주면 문자열의 첫 글자와 마지막 글자를 출력하는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 하나의 문자열이 주어진다. 문자열은 알파벳 A~Z 대문자로 이루어지며 알파벳 사이에 공백은 없으며 문자열의 길이는 1000보다 작다.
출력
각 테스트 케이스에 대해서 주어진 문자열의 첫 글자와 마지막 글자를 연속하여 출력한다.
예제 입력 1
3
ACDKJFOWIEGHE
O
AB
예제 출력 1
AE
OO
AB풀이
문자열을 입력받은 뒤 인덱스 0과 인덱스 (문자열 크기 - 1)을 출력하면 되는 문제이다.
#include <iostream>
using namespace std;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
cout << s[0] << s[s.size() - 1] << '\n';
}
}
30589
문제
Маска для монстров
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 72 51 33 67.347%
문제
몬스터들도 잠이 필요하지만 모든 몬스터가 쉽게 잠들 수 있는 것은 아니다. 평면 위에 있는 N개의 꼭짓점으로 이루어진 볼록 다각형 모양의 몬스터 바딤은 종종 빛 때문에 잠을 이루지 못한다. 바딤에게는 N개의 눈이 있으며, 각 꼭짓점에 하나씩 위치해 있다. 바딤이 편안하게 잠들기 위해서는 모든 눈을 덮을 수 있는 몬스터용 마스크가 필요하다. 몬스터용 마스크는 임의의 선으로, 각 눈에 꼭 맞아야 하고 다각형 내부를 통과해서는 안 된다. 상점에는 다양한 마스크가 있지만, 바딤에게는 최소 길이의 마스크만 있으면 충분하다. 이 마스크의 길이는 얼마인가?
입력
첫 번째 줄에 정수 N이 주어진다 — 몬스터의 눈의 개수 (3 <= N <= 10^5).
그다음 각 줄마다 두 개의 정수 x_i, y_i가 공백으로 구분되어 주어진다 — 다각형의 꼭짓점 좌표가 반시계 방향으로 주어진다 (-10^9 <= x_i, y_i <= 10^9).
다각형이 볼록함이 보장된다.
출력
바딤에게 적합한 최소 길이의 마스크를 출력한다.
출력값은 절대 또는 상대 오차가 10^{-6}을 넘지 않아야 한다.
예제 입력 1
4
0 0
2 0
2 2
0 2
예제 출력 1
6.000000풀이
주어지는 점들이 반시계방향으로 주어진다.
그렇기에 점들을 따라 한 바퀴를 돌면서 점 사이의 거리를 다 더한 이후에 점 사이의 거리의 최댓값을 빼면
가장 짧은 마스크의 길이를 구할 수 있다.
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
long double ans;
long double m;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<pair<long double, long double>> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
}
for (int i = 0; i < n; i++) {
int next = (i + 1) % n;
long double x = points[i].first - points[next].first;
long double y = points[i].second - points[next].second;
ans += sqrt(x * x + y * y);
m = max(m, sqrt(x * x + y * y));
}
ans -= m;
cout.precision(10);
cout << ans << '\n';
return 0;
}
15719
문제
중복된 숫자 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 256 MB 9149 2098 1393 23.259%
문제
1부터 N - 1까지의 정수가 하나씩 정렬되지 않은 채로 저장되어 있는 어떤 수열 A가 있다. 수열 A에 임의의 정수 M(1 ≤ M ≤ N – 1)을 넣어 크기가 N인 수열로 만들었을 때, 임의의 정수 M을 찾는 프로그램을 작성하라.
입력
첫째 줄에 수열의 크기 N(2 ≤ N ≤ 10,000,000)이 주어진다.
둘째 줄에 수열 A의 원소인 N개의 정수가 주어진다. 입력으로 주어지는 정수는 모두 1보다 크거나 같고, N-1보다 작거나 같은 정수이며 문제의 답인 M을 제외하고는 모두 서로 다른 정수이다.
출력
M을 출력하라.
예제 입력 1
10
1 2 2 5 6 4 3 7 8 9
예제 출력 1
2풀이
벡터에 입력받은 값들을 추가한 다음 오름차 순으로 정렬한다.
인덱스 + 1과 벡터의 값이 동일하지 않다면 그 값이 M이기 때문에 출력하면 된다.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long n;
cin >> n;
vector<long long> num;
for (long long i = 0; i < n; i++) {
int temp;
cin >> temp;
num.push_back(temp);
}
sort(num.begin(), num.end());
for (long long i = 0; i < n; i++) {
if ((i + 1) != num[i]) {
cout << i;
break;
}
}
return 0;
}
15803
문제
PLAYERJINAH’S BOTTLEGROUNDS 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 2005 841 745 42.426%
문제
한때 굉장히 유행하고 유명했던 게임, PLAYERJINAH’S BOTTLEGROUNDS는 FPS(First-Person Shooter) 장르의 게임이다. 전 세계적으로 많은 사람을 열광시킨 이 게임은 영화 Bottle Royale 을 모티브로 만들어졌다. 영화 Bottle Royale 에서는 한 학급의 학생들을 한 섬에 가두고, 그들에게 각자 병을 지급한 뒤, 단 한 명의 승자가 남을 때까지 서로 병 던지기를 시키는 내용이 나온다. 이 게임은 그와 비슷하게 100명의 플레이어가 각자 거대한 수송기에서 낙하산으로 낙하하여 한 명의 승자가 남을 때까지 진행된다.
이 게임을 즐기는 진아는 굉장한 실력의 게이머로서, 그녀의 실력은 화면 속의 적을 동시에 3명까지 맞춰 쓰러뜨릴 정도로 잘한다. 대신에 그녀가 제 실력을 발휘하기 위해선 한 가지 조건이 있다. 그건 적들이 진아의 화면 속에서 직선으로 있을 때만 동시에 쓰러뜨릴 수 있다는 것인데, 몇 번의 승부로 이를 알아챈 준서는 BOTTLEGROUNDS 대회에서 진아를 쓰러뜨리고 우승하기 위해 같은 스쿼드의 팀원들과 특훈을 시작했다. 특훈 내용은 상대방의 화면 속에서 각자의 위치가 직선이 안 되도록 포지션을 잡는 것이다. 준서는 이 연습을 위해서 당신에게 현재 팀원들의 상대방 화면 속 위치들이 직선이 되는지를 판별하는 기계를 만들어 달라고 요청했다. 당신에게 의뢰비로 대회 상금의 30%를 약속했기 때문에 당신은 흔쾌히 제안을 수락했다. 이제 그들에게 전달할 기계의 프로그램을 만들어 보도록 하자.
입력
프로그램의 입력은 표준 입력으로 받는다. 스쿼드는 총 4명으로 구성되며 준서는 멀리서 저격을 하기 때문에 좌표가 주어지지 않는다. 따라서 첫 번째 줄부터 세 번째 줄까지 x, y (1 ≤ x, y ≤ 1000) 두 개의 자연수가 각각 주어진다. 각 줄의 x, y는 한 명의 팀원이 상대방 화면에서 어떤 위치인지 나타낸다. 그리고 팀원들은 항상 서로 다른 위치에 있다.
출력
프로그램의 출력은 표준 출력으로 한다. 팀원의 위치가 직선이 될 때 ‘WHERE IS MY CHICKEN?’ 을, 아닌 경우 ‘WINNER WINNER CHICKEN DINNER!’ 를 출력한다.
예제 입력 1
1 1
1 2
2 1
예제 출력 1
WINNER WINNER CHICKEN DINNER!
예제 입력 2
12 10
24 20
36 30
예제 출력 2
WHERE IS MY CHICKEN?
풀이
세 점이 이루는 세 직선의 기울기가 동일한지 확인하면 된다.
사실 두 직선만 동일한지 확인해도 괜찮을 것 같다.
점이 입력되는 순서에 따라서 -inf와 +inf가 기울기로 나타날 수 있는데,
그때만 예외처리를 하여서 해결하였다.
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<pair<double, double>> pos;
vector<double> gradient;
for (int i = 0; i < 3; i++) {
double x, y;
cin >> x >> y;
pos.push_back(make_pair(x, y));
}
for (int i = 0; i < 3; i++) {
int next = (i + 1) % 3;
double g =
(pos[i].second - pos[next].second) / (pos[i].first - pos[next].first);
if (g == -1 * numeric_limits<double>::infinity()) {
g = numeric_limits<double>::infinity();
}
gradient.push_back(g);
for (int j = 0; j < gradient.size(); j++) {
if (gradient[j] != g) {
cout << "WINNER WINNER CHICKEN DINNER!";
return 0;
}
}
}
cout << "WHERE IS MY CHICKEN?";
return 0;
}
24315
문제
알고리즘 수업 - 점근적 표기 3
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 334 247 218 75.958%
문제
오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
알고리즘의 소요 시간을 나타내는 Θ-표기법(빅-쎄타)을 다음과 같이 정의한다.
Θ(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 c1 × g(n) ≤ f(n) ≤ c2 × g(n)인 양의 상수 c1, c2, n0가 존재한다}
이 정의는 실제 Θ-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.
함수 f(n) = a1n + a0, 양의 정수 c1, c2, n0가 주어질 경우 Θ(n) 정의를 만족하는지 알아보자.
입력
첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
다음 줄에 양의 정수 c1, c2가 주어진다. (1 ≤ c1 ≤ c2 ≤ 100)
다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)
출력
f(n), c1, c2, n0가 Θ(n) 정의를 만족하면 1, 아니면 0을 출력한다.
예제 입력 1
7 -7
6 8
1
예제 출력 1
0
f(n) = 7n - 7, g(n) = n, c1 = 6, c2 = 8, n0 = 1이다. f(1) = 0, c1 × g(1) = 6이므로 Θ(n) 정의를 만족하지 못한다.
예제 입력 2
7 -7
6 8
10
예제 출력 2
1
f(n) = 7n - 7, g(n) = n, c1 = 6, c2 = 8, n0 = 10이다. 모든 n ≥ 10에 대하여 6n ≤ 7n - 7 ≤ 8n이므로 Θ(n) 정의를 만족한다.풀이
두 부등호를 계산해서 조건을 만족하는지 확인하면 되는 문제이다.
간단쓰
#include <iostream>
using namespace std;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a1, a0, c1, c2, n;
cin >> a1 >> a0 >> c1 >> c2 >> n;
if (n * (a1 - c1) + a0 >= 0 && a1 - c1 >= 0) {
if (n * (c2 - a1) - a0 >= 0 && c2 - a1 >= 0) {
cout << 1;
return 0;
}
}
cout << 0;
return 0;
}
11366
문제
Tons of Orcs, no Fibbin’
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 594 116 88 23.037%
문제
모르도르의 군대는 그 크기와 숫자에서 모두 무서운 존재이다. 어떻게 그렇게 짧은 시간에 엄청난 군세를 일으킬 수 있었을까? 그 이유는 오크들이 매우 빠르게 번식하기 때문이다. 어떤 해의 오크 수는 이전 두 해의 오크 수의 합과 같다. 예를 들어, 7년 차에 오크가 14마리이고 8년 차에 오크가 20마리라면, 9년 차에는 총 34마리의 오크 수를 계산할 수 있고, 10년 차에는 총 54마리가 된다. 이전 두 해의 오크 수가 주어질 때, n년 후의 오크 수를 계산하라.
입력
각 테스트 케이스는 한 줄로 주어지며, 형태는 a b c이다. 여기서 a와 b는 이전 두 해의 오크 수를 나타내는 0 이상의 정수이며, c는 미래 몇 년 후의 오크 수를 계산할지를 나타내는 정수이다. 입력의 끝은 0 0 0 형식의 한 줄로 표시되며, 이 줄은 출력을 생성하지 않아야 한다. 모든 값은 int 변수에 저장할 수 있는 값을 넘지 않는다.
출력
각 테스트 케이스마다, 지정된 해의 오크 수를 나타내는 정수를 한 줄에 출력한다. 모든 값은 int 변수에 저장할 수 있는 값을 넘지 않는다.
예제 입력 1
10 10 1
0 39 4
14 20 1
0 0 0
예제 출력 1
20
195
34풀이
피보나치를 활용해서 풀면 되는 문제이다.
int 범위를 넘기지 않는다고 문제에 쓰여있기에 굳이 long long도 쓸 이유 없었음.
a, b가 0이고 c가 너무 큰 값을 가질 때 시간초과가 나서 a, b가 0일 때만 예외처리해서 해결했다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c;
while (cin >> a >> b >> c) {
if (a == 0 && b == 0 && c == 0) {
break;
}
// 이 코드 없으면 시간 초과
if (a == 0 && b == 0) {
cout << 0 << '\n';
continue;
}
for (long long i = 0; i < c; i++) {
int temp = a + b;
a = b;
b = temp;
}
cout << b << '\n';
}
}
12933
문제
오리
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 6203 2068 1567 33.591%
문제
오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.
영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.
갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.
녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.
영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다.
출력
영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.
예제 입력 1
quqacukqauackck
예제 출력 1
2
예제 입력 2
kcauq
예제 출력 2
-1
예제 입력 3
quackquackquackquackquackquackquackquackquackquack
예제 출력 3
1
예제 입력 4
qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk
예제 출력 4
10
예제 입력 5
quqaquuacakcqckkuaquckqauckack
예제 출력 5
3
예제 입력 6
quackqauckquack
예제 출력 6
-1풀이
울음 소리를 오리에 맞게 배정하다가 배정되지 않은 울음 소리가 나오면 -1 출력.
모든 울음 소리를 배정한 이후 quack이 완성되지 않은 울음 소리가 나오면 -1 출력.
정답은 매 반복마다 max 비교를 통해 저장.
#include <iostream>
#include <vector>
using namespace std;
string s;
vector<string> cnt;
int count;
int ans;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> s;
for (int i = 0; i < s.size(); i++) {
int flag = 0;
if (s[i] == 'q') {
cnt.push_back("q");
count++;
flag = 1;
}
if (s[i] == 'u') {
for (int j = 0; j < cnt.size(); j++) {
if (cnt[j].back() == 'q') {
cnt[j].push_back('u');
flag = 1;
break;
}
}
}
if (s[i] == 'a') {
for (int j = 0; j < cnt.size(); j++) {
if (cnt[j].back() == 'u') {
cnt[j].push_back('a');
flag = 1;
break;
}
}
}
if (s[i] == 'c') {
for (int j = 0; j < cnt.size(); j++) {
if (cnt[j].back() == 'a') {
cnt[j].push_back('c');
flag = 1;
break;
}
}
}
if (s[i] == 'k') {
for (int j = 0; j < cnt.size(); j++) {
if (cnt[j].back() == 'c') {
count--;
flag = 1;
cnt[j].push_back('k');
break;
}
}
}
if (!flag) {
cout << -1;
return 0;
}
ans = max(ans, count);
}
for (int i = 0; i < cnt.size(); i++) {
if (cnt[i].back() != 'k') {
cout << -1;
return 0;
}
}
cout << ans;
return 0;
}
12842
문제
튀김 소보루
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 1285 429 320 35.398%
문제
영선이는 대전에 내려갔다 서울 오는 길에 튀김 소보루 n개를 사왔다. (1 ≤ n ≤ 100,000)
영선이가 SCCC 회원들에게 나누어 주기 위하여 001에 두고 잠깐 나갔다 온 사이에 온전한 튀김 소보루는 s개가 남아 있었다.(먹기 위해 집어 든 튀김소보루는 제외한다)
영선이가 자리를 비운 동안 001에는 m명이 있었고, 각 사람은 1부터 m번까지 번호가 매겨져 있다. 영선이는 평소에 SCCC 회원들과 식사를 자주해서 식사 속도를 알고 있다. 이를 바탕으로 튀김 소보루 1개를 먹는데 걸리는 시간을 유추할 수 있다.
영선이를 위해 이 정보들을 바탕으로 마지막으로 튀김 소보루를 집어 든 사람의 번호를 구하여라.
여러 사람이 동시에 소보루를 집는다면 번호가 작은 사람이 먼저 잡으며, 영선이가 떠나자 마자 바로 먹기를 시작한다.
예를 들어, 소보루를 먹는 시간이 1번은 1초, 2번은 3초, 3번은 5초에 하나씩 먹는다고 하고, 소보루는 1000개 있다고 하자.
1개가 줄었다면 1번 사람이 처음 빵을 집을 것이다.
2개가 줄었다면 2번 사람이 1번 사람이 집은 직후 처음 빵을 집을 것이다.
3개가 줄었다면 3번 사람이 2번 사람이 집은 직후 처음 빵을 집을 것이다.
4개가 줄었다면 1번 사람이 빵을 다 먹고, 2개째 빵을 집을 것이다.
5개가 줄었다면 1번 사람이 빵을 다 먹고, 3개째 빵을 집을 것이다.
6개가 줄었다면 1번 사람이 빵을 다 먹고, 4개째 빵을 집을 것이다.
7개가 줄었다면 2번 사람이 빵을 다 먹고 1번 사람이 집은 직후, 2개째 빵을 집을 것이다.
입력
첫 번째 줄에 n s 가 주어진다. n은 영선이가 사온 튀김 소보루의 개수이다.
s는 영선이가 돌아왔을 때 남아 있던 튀김 소보루의 개수이다. (0 ≤ s ≤ n-1)
두 번째 줄 에는 m (1 ≤ m ≤ 100,000) 이 주어지고 , 다음 m 개의 줄 에는 1번부터 m번까지의 사람이 한 개의 소보루를 먹는데 걸리는 시간 ti(초) 가 주어진다. (1 ≤ ti ≤ 1,000)
출력
마지막으로 소보루를 집어 든 사람의 번호를 출력한다.
예제 입력 1
1000 975
3
1
3
5
예제 출력 1
2풀이
처음에는 벡터에 저장한 다음에 브루트포스로 풀려했는데 시간초과났다.
십만 * 십만이라 짐작은 했는데...
브루트포스로 푼 정답이 있는걸로 보아 벡터가 아니라 배열을 사용하면 맞았을 듯.
아래는 오답 코드.
#include <iostream>
#include <vector>
using namespace std;
vector<int> time;
vector<int> hold;
int n, s, m, ans;
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> s >> m;
time.resize(m);
hold.resize(m, 0);
for (int i = 0; i < m; i++) {
cin >> time[i];
}
for (int i = 0; i < n - s; i++) {
int start = 0;
for (int j = 0; j < m; j++) {
if (hold[j] == 0) {
hold[j] = time[j];
ans = j;
start = 1;
break;
}
}
if (start == 0) {
for (int j = 0; j < m; j++) {
hold[j]--;
}
}
}
cout << ans + 1 << '\n';
}이후에 이진탐색으로 맞음
#include <iostream>
#include <vector>
using namespace std;
vector<int> time;
int n, s, m;
bool canEatAll(int mid) {
long long total = 0;
for (int i = 0; i < m; i++) {
total += mid / time[i] + 1;
if (total >= (n - s))
return true;
}
return total >= (n - s);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> s >> m;
time.resize(m);
for (int i = 0; i < m; i++) {
cin >> time[i];
}
int left = 0, right = 1e9, last_time = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (canEatAll(mid)) {
right = mid - 1;
last_time = mid;
} else {
left = mid + 1;
}
}
int eaten = 0;
int last_person = -1;
while (eaten < (n - s)) {
for (int i = 0; i <= last_time; i++) {
for (int j = 0; j < m; j++) {
if (i % time[j] == 0) {
eaten++;
if (eaten == (n - s)) {
last_person = j + 1;
break;
}
}
}
}
}
cout << last_person << '\n';
return 0;
}
'Algorithm > BOJ' 카테고리의 다른 글
블로그의 정보
공부중임
구설구설