[BOJ] 랜덤 마라톤 (No. 30402, 18268, 3135, 2545, 5230, 5581, 26011, 23732)
by 구설구설30402
문제
감마선을 맞은 컴퓨터
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 2414 1524 1449 65.300%
문제
춘배와 나비, 영철은 어느 날 지구에 나타난 UFO에게 감마선을 맞을 뻔했다. 다행히도 감마선은 행복하게 뒹굴고 있던 고양이들 옆에 있던 컴퓨터에 맞았지만, 이로 인해 컴퓨터에 저장된 춘배와 나비, 영철의 소중한 사진들의 픽셀이 모두 섞이는 사태가 발생했다! 더 이상 형체를 알아볼 수 없게 된 사진들을 보며 슬퍼하던 고양이들은 사진 복구로 유명한 전문가에게 사진의 복구를 맡기기로 했다. 자신의 사진을 다른 고양이가 보는 게 싫었던 춘배는 사진 복구를 맡기기 전에 당신에게 사진을 분류해 주는 프로그램을 만들어 달라고 부탁하였다.
프로그램은 주어진 사진이 어떤 고양이의 사진인지 구분해야 한다. 하얀색(w)이 존재한다면 춘배, 검은색(b)이 존재한다면 나비, 회색(g)이 존재한다면 영철의 사진이다. 사진은 고양이(w, b, g) 또는 배경(r, o, y, p)으로 이루어져 있으며 한 사진에 고양이는 무조건 1마리만 나온다.
입력으로 주어진 사진이 어떤 고양이의 사진인지 구분해 주자.
입력
15줄에 걸쳐 한 줄에 15개씩 섞여버린 사진의 픽셀 색이 공백으로 구분되어 주어진다.
출력
춘배의 사진이라면 chunbae, 나비의 사진이라면 nabi, 영철의 사진이라면 yeongcheol을 출력한다.
예제 입력 1
p o o y r y p o y r p r r o p
y w w y w r w y w p w w w r y
r w y r w r w w w y r p w w o
r p w w w w w y w w o w o r w
y w w w r o p w o r r w p p w
y y w w w o w p o w r p p o o
p w p w p y o p w w w w p y w
y w y o w o w o o o w o w w p
y o w w y w w w r w o p w w p
p w p y w w o w o r w w p r y
p p w w w w y r w w w y y o w
p w p w w w w o o p o w p w p
y p o y w p w w w w w w r w p
p y r w w w w w o w w p o y w
o r w w y y y w w o o y y r w
예제 출력 1
chunbae풀이
입력을 모두 받은 뒤 ~w~, ~b~, ~g~이 있는지 확인한 뒤 출력한다.
#include <bits/stdc++.h>
using namespace std;
vector<char> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 225; i++) {
char c;
cin >> c;
v.push_back(c);
}
if (find(v.begin(), v.end(), 'w') != v.end()) {
cout << "chunbae" << '\n';
} else if (find(v.begin(), v.end(), 'b') != v.end()) {
cout << "nabi" << '\n';
} else if (find(v.begin(), v.end(), 'g') != v.end()) {
cout << "yeongcheol" << '\n';
}
return 0;
}
18268
문제
Cow Gymnastics
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 1369 722 628 55.822%
문제
체력을 기르기 위해 소들이 체조를 시작했다. 농부 John은 가장 좋아하는 소 Bessie를 코치로 지정하고, 나머지 N마리 소들의 실력을 평가하도록 하였다. K번의 연습 세션에서 Bessie는 N마리의 소들을 실력 순으로 정렬하였다.
Bessie는 각 소의 순위가 얼마나 일관성 있는지 궁금해졌다. 두 마리의 소 A와 B가 "일관된 쌍"이라고 할 때, 이는 A가 모든 연습 세션에서 B보다 항상 더 잘한 경우를 의미한다.
Bessie가 "일관된 쌍"의 총 개수를 계산할 수 있도록 도와라.
입력
첫 번째 줄에는 두 개의 정수 K와 N이 주어진다.
다음 K줄에는 1부터 N까지의 정수가 임의의 순서로 주어지며, 이는 각 연습 세션에서의 소들의 순위를 나타낸다. A가 B보다 먼저 나타나면, 이는 A가 B보다 더 잘했다는 것을 의미한다.
( 1 <= K <= 10 )
( 1 <= N <= 20 )
출력
일관된 쌍의 개수를 한 줄에 출력한다.
예제 입력 1
3 4
4 1 2 3
4 1 3 2
4 2 1 3
예제 출력 1
4
힌트
일관된 쌍: ((1, 4), (2, 4), (3, 4), (1, 3))
각각의 쌍은 모든 세션에서 같은 순서를 유지한다.풀이
~vector<vector<int>> v~에 각 줄 별로 소의 순서를 집어 넣는다.
이후 이중 for 문을 통해 두 소를 모든 줄에 거쳐서 순서의 일관성이 있는지 확인한다.
#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
vector<vector<int>> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
v.resize(n);
for (int i = 0; i < n; i++) {
v[i].resize(k);
for (int j = 1; j < k + 1; j++) {
int temp;
cin >> temp;
v[i][temp - 1] = j;
}
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (i == j) continue;
bool flag = true;
for (int l = 0; l < n; l++) {
if (v[l][i] >= v[l][j]) {
flag = false;
break;
}
}
if (flag) {
ans++;
}
}
}
cout << ans;
return 0;
}
3135
문제
라디오
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 4522 2777 2506 62.214%
문제
준하는 라디오 수집광으로 신제품의 라디오가 나올때마다 흥분을 금치 못한다고 한다.
최근 준하가 구입한 라디오는 매우 하이테크 한데, 그 라디오에는 다음과 같은 버튼이 있다.
첫 번째 버튼은 주파수를 1MHz 증가시킨다.
두 번째 버튼은 주파수를 1MHz 감소시킨다.
나머지 N개의 버튼은 즐겨찾기 기능으로, 미리 지정된 주파수로 이동한다.
준하는 몸이 안좋아 하루에 손가락을 몇 번 움직이지 못하기 때문에 우리의 도움이 필요하다.
현재 주파수 A와 듣고싶은 주파수 B가 주어질 때,
주파수 A에서 B로 갈 때 눌러야 하는 가장 적은 버튼수를 구해주자.
입력
첫 줄엔 정수 A와 B가 주어진다 (1 ≤ A, B < 1000, A ≠ B).
다음 줄엔 정수 N이 주어진다 (1 ≤ N ≤ 5).
다음 N개의 줄엔 미리 지정되어 있는 주파수가 주어진다 (주파수는 1000 보다 작다).
출력
주파수 A에서 B로 갈 때 눌러야 하는 버튼수의 최솟값을 출력한다.
예제 입력 1
100 15
1
15
예제 출력 1
1
예제 입력 2
88 17
3
18
1
42
예제 출력 2
2
예제 입력 3
64 120
1
567
예제 출력 3
56풀이
처음 라디오 주파수와 목표 주파수의 차를 정답의 초기값으로 설정한다.
이후에 입력되는 버튼의 주파수와 목표 주파수의 차 +1과 정답을 비교하여 더 작은 값을 계속 선택한다.
#include <bits/stdc++.h>
using namespace std;
int n, ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b;
cin >> a >> b;
ans = abs(a - b);
cin >> n;
for (int i = 0; i < n; i++) {
int f;
cin >> f;
ans = min(ans, abs(b - f) + 1);
}
cout << ans << '\n';
}
2545
문제
팬케익 먹기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 1249 256 224 27.350%
문제
오늘 아침 은주는 팬케익을 만들었다. 자 이제 신혜는 이 팬케익을 먹으려고 한다.
은주가 만든 팬케익은 박스 모양이고, 가로 Acm, 세로 Bcm, 높이 Ccm 크기이다.
신혜는 팬케익을 D번 먹으려고 한다. 매번 신혜가 팬케익을 먹으려고 할 때, 은주는 팬케익을 변에 평행하게 자른 후에 신혜에게 준다.
은주는 뛰어난 요리사이기 때문에, 자르는 케익은 모두 두께가 1cm이다.
원래 은주는 팬케익을 다 먹으려고 했으나, 어쩔수 없이 신혜에게 주는 것이다. 따라서, 최대한 많은 양을 남기려고 한다.
신혜가 팬케익을 D번 먹은 후에 남은 케익의 양은 은주가 케익을 자르는 방법에 따라서 달라지게 된다.
A, B, C, D가 주어졌을 때, 신헤가 팬케익을 D번 먹은 후에 남은 팬케익 부피의 가능한 최댓값을 구하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 빈 줄로 구분되며, 다음과 같이 구성되어 있다.
테스트 케이스의 첫째 줄에 A, B, C, D가 주어진다.
출력
각 테스트 케이스에 대해 은주가 남길 수 있는 팬케익의 최대 부피를 차례대로 한 줄에 하나씩 출력한다. 이 부피는 부호있는 64비트 정수 범위 안에 들어온다.
제한
0 ≤ D ≤ A + B + C - 3
서브태스크
번호 배점 제한
Easy 1
0 < A, B, C ≤ 1000
Hard 2
0 < A, B, C ≤ 10^18
예제 입력 1
3
4 5 6 0
4 5 6 3
1 1 10 9
예제 출력 1
120
64
1
힌트
두 번째 테스트 케이스를 보자. 왜 정답이 64일까? 가장 먼저 4 * 5 변에 맞춰서 2번 팬케익을 자르면 남은 팬케익은 4*5*4가 된다. 그 다음에 4 * 4 변에 맞추어 팬케익을 자르면 4*4*4가 된다. 따라서 64이다.풀이
팬케익의 부피를 최대로 만들기 위해서는 가로, 세로, 높이 중 가장 긴 변이 줄어드는 방식으로 잘라야만 한다.
1점을 받는 경우에는 그냥 for문을 사용해서 매 번 가장 긴 변을 줄이면 된다.
#include <bits/stdc++.h>
using namespace std;
long long n, a, b, c, d;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (long long j = 0; j < n; j++) {
cin >> a >> b >> c >> d;
for (long long i = 0; i < d; i++) {
long long m = max(a, max(b, c));
if (m == a) {
a--;
} else if (m == b) {
b--;
} else {
c--;
}
}
cout << a * b * c << '\n';
}
}3점을 받기 위해서는 이런 식의 $O(n) $이 아니라, 입력 값이 어마어마한 것을 고려하여 $ O(1) $로 실행되어야 한다.
즉, 입력값만 가지고 한 번에 해결하도록 분기 설정을 해줘야 한다는 뜻이다.
- 가장 큰 값에서 만큼 차감 가능한 경우
- 가장 큰 값에서 차감.
- 가장 큰 값과 두 번째 값에서 차감 가능한 경우
- 가장 큰 값에서 가능한 만큼 먼저 차감한 이후, 남은 d를 가장 큰 값과 중간값에서 차감한다.
- ~남은 d % 2~가 0이면 나머지를 균등하게 나누어 차감한다.
- ~남은 d % 2~가 1이면 한 쪽을 1 더 차감한다.
- 세 값을 모두 차감해야 하는 경우
- 모든 값이 가장 작은 값과 동일하도록 차감한다.
- ~남은 d % 3~의 값에 따라 처리한다.
#include <bits/stdc++.h>
using namespace std;
long long n, d;
vector<long long> v(3);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (long long j = 0; j < n; j++) {
cin >> v[0] >> v[1] >> v[2] >> d;
sort(v.begin(), v.end());
long long firstminussecond = v[2] - v[1];
long long secondminusthird = v[1] - v[0];
long long firstminusthird = v[2] - v[0];
if (firstminussecond >= d) {
cout << (v[2] - d) * v[1] * v[0] << '\n';
} else if (firstminusthird + secondminusthird >= d) {
v[2] -= firstminussecond;
d -= firstminussecond;
if (d % 2 == 0) {
cout << (v[2] - d / 2) * (v[1] - d / 2) * v[0] << '\n';
} else {
cout << (v[2] - d / 2) * (v[1] - d / 2 - 1) * v[0] << '\n';
}
} else {
v[2] -= firstminusthird;
v[1] -= secondminusthird;
d -= (firstminusthird + secondminusthird);
if (d % 3 == 0) {
cout << (v[2] - d / 3) * (v[1] - d / 3) * (v[0] - d / 3) << '\n';
} else if (d % 3 == 1) {
cout << (v[2] - d / 3) * (v[1] - d / 3) * (v[0] - d / 3 - 1) << '\n';
} else {
cout << (v[2] - d / 3) * (v[1] - d / 3 - 1) * (v[0] - d / 3 - 1)
<< '\n';
}
}
}
}
5230
문제
Prefix Codes
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 142 69 57 53.774%
문제
샘(Sam)은 외부 세계와 통신할 수 있는 오래된 통신 채널을 발견했다. 하지만 이 채널은 매우 느려서, 샘과 친구들은 메시지를 더 빠르게 전송하기 위해 압축 코드를 사용하려고 한다. 오랜 고민 끝에 샘은 바이너리 접두사 코드(binary prefix code)를 사용하기로 결정했다.
접두사 코드(prefix code)는 가변 길이 코드 시스템으로, 이 시스템 내의 유효한 어떤 코드도 다른 코드의 접두사가 될 수 없는 특성을 가진다. 예를 들어, {a=0, b=10, c=11}은 접두사 코드이지만, {a=0, b=10, c=01}은 접두사 코드가 아니다. 왜냐하면 0이 01의 접두사이기 때문이다.
바이너리 접두사 코드(binary prefix code)는 바이너리 트리로 표현할 수 있다. 이 트리에서 각 심볼은 잎(leaf)에 위치하고, 루트에서 잎까지의 경로가 해당 심볼의 코드를 나타낸다. 트리에서 왼쪽 자식으로 이동할 때는 0, 오른쪽 자식으로 이동할 때는 1이 사용된다. 예를 들어, {a=0, b=10, c=11}과 {a=000, b=001, c=01, d=10, e=110, f=111}은 아래와 같이 트리로 표현할 수 있다.
입력
입력은 여러 테스트 케이스로 구성된다.
첫 번째 줄에는 테스트 케이스의 개수(< 100)가 주어진다.
이후 각 줄에는 하나의 테스트 케이스가 주어진다.
각 테스트 케이스는 k, 접두사 코드의 문자열 표현, 그리고 k개의 바이너리 문자열이 주어진다.
접두사 코드는 *로 내부 노드나 누락된 노드를 나타내고, 잎에는 실제 문자가 위치한다.
각 디코딩할 문자열은 접두사 코드에 나오는 문자들로만 이루어져 있다.
출력
각 테스트 케이스에 대해 디코딩된 문자열을 출력한다.
출력은 각 테스트 케이스 별로 한 줄에 디코딩된 문자열을 공백으로 구분해 출력한다.
예제 입력 1
4
3 *a***bc 0 10 11
2 *a***bc 11010 010100
6 ****cd*ab****ef 000 001 01 10 110 111
5 ****cd*ab****ef 11100001110 000 00100010 01000111110 001110110
예제 출력 1
a b c
cab abba
a b c d e f
face a bad cafe bee풀이
루트 노드 부터 시작해서 아래로 트리를 내려가면서 탐색 한다.
문자를 발견하면 문자를 출력하고 다시 루트 노드부터 탐색을 시작한다.
비트로 표현된 문자열이 끝날 때마다 띄어쓰기를 한다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
string tree;
cin >> n >> tree;
for (int i = 0; i < n; i++) {
int x = 0;
string s;
cin >> s;
if (i > 0) cout << ' ';
for (int j = 0; j < s.size(); j++) {
x = x * 2 + 1;
if (s[j] == '1') x++;
if (tree[x] != '*') {
cout << tree[x];
x = 0;
}
}
}
cout << '\n';
}
return 0;
}
5581
문제
碁石ならべ
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 95 45 40 54.795%
흰색과 검은색 바둑돌을 테이블 위에 나열하며 놀고 있다. 다음과 같은 규칙으로 바둑돌을 놓는다:
테이블의 왼쪽 끝부터 바둑돌을 놓기 시작한다.
왼쪽에서 두 번째 위치에 바둑돌을 놓는다.
이를 n번 반복하여 n개의 바둑돌을 일렬로 나열한다.
단, 새로운 i번째 바둑돌을 놓을 때는 다음 규칙에 따른다:
i가 홀수일 경우: 테이블 위의 기존 바둑돌은 변경하지 않고, 새로운 바둑돌을 왼쪽에서 i번째 위치에 놓는다.
i가 짝수일 경우:새로운 i번째 바둑돌의 색상과 테이블 위의 오른쪽 끝 바둑돌의 색상이 같다면 기존 바둑돌은 변경하지 않고, 새로운 바둑돌을 왼쪽에서
i번째 위치에 놓는다.
새로운 i번째 바둑돌의 색상과 테이블 위 오른쪽 끝 바둑돌의 색상이 다를 경우:
테이블 오른쪽 끝의 같은 색으로 연속된 바둑돌을 모두 제거한다.
제거된 바둑돌의 위치에 i번째 바둑돌과 같은 색상의 바둑돌로 바꾼다.
오른쪽 끝에 i번째 바둑돌을 놓는다.
예를 들어, 처음 7개의 바둑돌을 놓은 후에 테이블 위가 다음과 같다고 가정하자:
○○●●○○○
8번째 바둑돌이 흰색(○)인 경우, 오른쪽 끝의 바둑돌과 색상이 같으므로 그대로 놓는다. 결과는 다음과 같다:
○○●●○○○○
8번째 바둑돌이 검은색(●)인 경우, 오른쪽 끝 바둑돌(○)과 색상이 다르므로 오른쪽 끝의 연속된 흰색 바둑돌 3개를 제거하고, 검은색 바둑돌로 대체한 후, 8번째 바둑돌을 놓는다. 결과는 다음과 같다:
○○●●●●●●
입력으로 n개의 바둑돌을 놓는 순서가 주어질 때, n개의 바둑돌을 모두 놓은 후 테이블 위에 있는 흰색 바둑돌의 개수를 구하는 프로그램을 작성하라.
입력
첫 번째 줄: 정수 n (1 ≤ 𝑛 ≤ 100,000)
두 번째 줄부터 n개의 줄: i번째 바둑돌의 색상을 나타내는 정수
c=0: 흰색 바둑돌
c=1: 검은색 바둑돌
출력
n개의 바둑돌을 모두 놓은 후 테이블 위에 있는 흰색 바둑돌의 개수를 나타내는 정수.
예제 입력 1
8
1
0
1
1
0
0
0
0
예제 출력 1
6
예제 입력 2
8
1
0
1
1
0
0
0
1
예제 출력 2
2풀이
연속된 같은 색상의 돌들을 하나의 요소로 관리하여 벡터에 저장한다.
- ~vector<pair<int, int>>~를 통해 ~(색상, 개수)~를 저장한다.
- 만약 돌 하나를 하나의 요소로 관리한다면 시간 초과가 발생한다. (최대 ~십만 * 십만~)
조건에 따라서 처리해주면 끝.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, ans = 0;
vector<pair<int, int>> board;
cin >> n;
for (int i = 1; i <= n; i++) {
int dol;
cin >> dol;
if (i % 2 == 1) {
if (!board.empty() && board.back().first == dol)
board.back().second++;
else
board.push_back({dol, 1});
} else if (board.back().first == dol) {
board.back().second++;
} else {
int cnt = 1;
while (!board.empty() && board.back().first != dol) {
cnt += board.back().second;
board.pop_back();
}
if (!board.empty() && board.back().first == dol) {
board.back().second += cnt;
} else {
board.push_back({dol, cnt});
}
}
}
for (int i = 0; i < board.size(); i++) {
if (board[i].first == 0) {
ans += board[i].second;
}
}
cout << ans << '\n';
}
26011
문제
문제
토마스는 여가 시간에 그의 다락방에 있는 방대한 레고 프로젝트를 즐기며 작은 도시의 집들을 하나씩 추가하는 것을 좋아한다. 그러나 그는 도시의 큰 바닥판에 있는 작은 돌기(stud) 때문에 강제로 직사각형 배열로 배치해야 하는 것에 약간 싫증이 났다.
다른 레고 제작자들과의 대화를 통해 토마스는 건물을 다른 각도로 배치할 수 있는 기술을 알게 되었다. 각 건물은 직사각형 모양의 바닥판(ground plate) 위에 놓이며, 이 바닥판 아래쪽 모서리에는 네 개의 원형 1×1 판(plate)이 부착된다. 이 판은 기본 바닥판의 네 개의 돌기에 정확히 맞게 배치된다. 그림 A.1과 같이 작동한다.
그림 A.1: 6×6 판을 대각선으로 배치한 모습.
만약 바닥판의 크기가 a×b일 때, 이 기술을 사용하여 모든 모서리 판이 기본 바닥판의 돌기에 정확히 맞도록 배치할 수 있는 서로 다른 방향의 개수를 구하시오.
그림 A.2는 첫 번째 예제 입력의 사례를 설명한 것이다. 6×11 판은 여러 방법으로 배치할 수 있지만, 서로 다른 방향은 단 6개뿐이다.
입력
입력은 한 줄로 주어진다:
두 정수 a와 b (2 ≤ a, b ≤ 10^6), 이는 건물이 놓인 바닥판의 크기를 나타낸다.
출력
모든 모서리 판이 기본 바닥판의 돌기에 정확히 맞도록 바닥판을 배치할 수 있는 서로 다른 방향의 개수를 나타내는 하나의 정수를 출력한다.
예제 입력 1
6 11
예제 출력 1
6
예제 입력 2
26 26
예제 출력 2
5
예제 입력 3
123 456
예제 출력 3
2
예제 입력 4
3 3
예제 출력 4
1
풀이
문제는 ~(w-1) * (h-1)~인 사각형을 배치하는 것과 동일하다.
한 모서리가 ~(0, 0)~에 있다고 가정하고,
$x^2 + y^2 = {(w-1)}^2$와 $x^2 + y^2 = {(h-1)}^2$를 만족시키는 정수 x,y를 각각 벡터에 저장한다.
이후 두 벡터에 저장된 x, y과 원점이 이루는 직선이 수직인지를 확인한다. 수직이라면 직사각형임을 의미한다.
만약 w와 h가 동일하다면 정답을 2로 나눈다.
#include <bits/stdc++.h>
using namespace std;
int ans;
long long w, h;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long w, h;
cin >> w >> h;
w--;
h--;
vector<pair<long long, long long>> wv;
vector<pair<long long, long long>> hv;
for (long long i = 0; i <= w; i++) {
if (sqrt(w * w - i * i) == (long long)sqrt(w * w - i * i)) {
wv.push_back({i, (long long)sqrt(w * w - i * i)});
if (sqrt(w * w - i * i) != 0 && i != 0) {
wv.push_back({i, -(long long)sqrt(w * w - i * i)});
}
}
}
for (long long i = 0; i <= h; i++) {
if (sqrt(h * h - i * i) == (long long)sqrt(h * h - i * i)) {
hv.push_back({i, (long long)sqrt(h * h - i * i)});
if (sqrt(h * h - i * i) != 0 && i != 0) {
hv.push_back({i, -(long long)sqrt(h * h - i * i)});
}
}
}
for (int i = 0; i < wv.size(); i++) {
for (int j = 0; j < hv.size(); j++) {
if (wv[i].first * hv[j].first + wv[i].second * hv[j].second == 0) {
ans++;
}
}
}
if (w == h) {
ans /= 2;
}
cout << ans;
}
23732
문제
Successful String
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음) 163 98 82 64.567%
문제
Yunee는 영어 단어를 공부하고 있으며, 그 중 "success"라는 단어를 가장 좋아하고, "failure"라는 단어를 가장 싫어한다.
Yunee는 "success"라는 단어에는 연속해서 같은 문자가 등장하는 위치가 있지만, "failure"라는 단어에는 그러한 부분이 없다는 것을 알아차렸다. 이에 따라 Yunee는 문자열 S 내에 어떤 위치 i가 있어서 S_i = S_{i+1}을 만족하는 경우, 해당 문자열 S를 "successful string"이라고 정의한다. 여기서 S_i는 문자열 S의 i번째 문자를 의미한다.
Yunee는 주어진 문자열의 부분문자열들 중에서 얼마나 많은 문자열이 "successful string"인지 알고자 한다. 서로 다른 시작 혹은 끝 인덱스를 가지면 비록 내용이 동일하더라도 다른 부분문자열로 간주한다. 이때 "successful string"인 부분문자열의 개수를 구하는 프로그램을 작성하라.
입력 형식
첫 번째 줄에 문자열의 길이 N이 주어진다. (1 <= N <= 10^6)
두 번째 줄에 길이 N인 소문자 알파벳으로 이루어진 문자열이 주어진다.
출력 형식
주어진 문자열의 모든 부분문자열 중에서 "successful string"의 개수를 출력한다.
예제 입력 1
7
success
예제 출력 1
15
"success"의 부분문자열 중 "ucc", "ccess", "ss" 등은 "successful string"의 예이며, "scc"는 "successful string"이지만 "success"의 부분문자열이 아니므로 제외된다.
예제 입력 2
7
failure
예제 출력 2
0
예제 입력 3
4
aaaa
예제 출력 3
6풀이
문자열의 길이가 n일 때 가능한 부분 문자열의 수는 $ n*(n+1)/2 $이다.
연속해서 동일한 문자가 나오는 지점을 기준으로 문자열을 끊었을 때, 그 사이 구간은 모두 연속 문자가 없는(=successful 하지 않는) 구간이다.
전체 부분 문자열 수에서 이런 구간들의 부분 문자열 수를 빼면 정답을 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
string s;
cin >> s;
long long total = (long long)n * (n + 1) / 2;
long long cnt_f = 0;
int start = 0;
for (int i = 1; i <= n; i++) {
if (i == n || s[i] == s[i - 1]) {
int length = i - start;
cnt_f += (long long)length * (length + 1) / 2;
start = i;
}
}
cout << total - cnt_f << "\n";
return 0;
}
블로그의 정보
공부중임
구설구설