문제 1
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
예제 입력 1
6
예제 출력 1
4
#include <iostream>
#include <queue>
using namespace std;
int a[500000];
queue<int> q;
int n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
q.push(i);
}
while(q.size() != 1 )
{
q.pop();
q.push(q.front());
q.pop();
}
cout << q.front();
}
문제 2
2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.
KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.
자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.
각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.
출력
첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.
예제 입력 1
5
1
5
3
1
2
예제 출력 1
3
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> a;
int n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
a.push_back(temp);
}
sort(a.begin(), a.end());
long long cnt = 0;
for (int i = 0; i < n; i++)
{
cnt += abs((i + 1) - a[i]);
}
cout << cnt;
}
문제 3
상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.
보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.
멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.
예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.
이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000)
다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다. 줄의 번호는 N보다 작거나 같은 자연수이고, 프렛의 번호도 P보다 작거나 같은 자연수이다.
출력
첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.
예제 입력 1
5 15
2 8
2 10
2 12
2 10
2 5
예제 출력 1
7
예제 입력 2
7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3
예제 출력 2
9
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
stack<int> m[10];
int n , P;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> P;
int a, b;
int cnt = 0;
for (int i = 0; i < n; i++)
{
cin >> a >> b;
if (m[a].empty()) // 아무것도 눌리지 않았고 처음 눌렸을 때.
{
m[a].push(b);
cnt++;
}
else if (m[a].top() < b) // 이미 키가 눌려져 있는 상태로 더 높은 키가 눌려졌을때.
{
m[a].push(b);
cnt++;
}
else if (m[a].top() > b) // 눌리고 있는 키보다 낮은 음을 눌렀을떄.
{
while (m[a].top() > b) // 줄에 눌린 손가락을 다 뗄때까지
{
m[a].pop();
cnt++;
if (m[a].empty()) // 누르려고 했던 키를 누름
{
m[a].push(b);
cnt++;
}
}
if (m[a].top() < b) // 누르고 있는 음이 치려는 음보다 작을떄
{
m[a].push(b);
cnt++;
}
}
}
cout << cnt;
}
BOJ 2606
문제 4
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제 입력 1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
예제 출력 1
4
BFS 구현
#include <iostream>
#include <queue>
using namespace std;
#define Max 101
int n, m;
int cnt = 0;
int arr[Max][Max];
bool visited[Max] = {0,};
queue<int> q;
void bfs(int node)
{
q.push(node);
visited[node] = true;
while (!q.empty())
{
node = q.front();
q.pop();
for (int i = 1; i <= n; i++)
{
if (arr[node][i] == 1 && visited[i] == 0) {
q.push(i);
visited[i] = true;
cnt++;
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
arr[x][y] = 1;
arr[y][x] = 1;
}
bfs(1);
cout << cnt;
}
문제 5
개의 줄마다 영어 대문자로만 이루어진 문자열 가 주어질 때, 각 줄마다 아래 조건을 모두 만족하는 문자열 를 출력하여라.
- 로 시작하여야 한다.
- 를 뒤에서부터 읽은 문자열 에 대해서도 로 시작하여야 한다.
- 위 조건을 만족하는 문자열이 여러 가지라면, 가장 길이가 짧은 문자열이 가 된다.
가능한 모든 에 대해서 조건을 만족하는 는 유일함을 증명할 수 있다.
입력
첫 번째 줄에 주어지는 문자열의 개수 가 주어진다. (1≤≤)
두 번째 줄부터 개의 줄에 걸쳐 문자열 가 주어진다. 각 줄마다 주어지는 문자열 의 길이는 이상 20이하이다.
출력
개의 줄에 걸쳐 주어진 문자열 마다 조건을 모두 만족하는 문자열 를 출력한다.
예제 입력 1
3
KITPA
BANANA
ROTATOR
예제 출력 1
KITPAPTIK
BANANAB
ROTATOR
풀이
#include <iostream>
using namespace std;
int T;
string X, S;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--)
{
cin >> S;
X = S;
int idx = 0;
while (true)
{
bool isequal = true;
for (int i = 0; i + idx < S.size(); i++)
{
if (S[i + idx] != S[S.size() - i - 1]) // 앞과 뒤
{
idx++;
isequal = false;
break;
}
}
if (isequal)
{
break;
}
}
for (int i = idx - 1; i >= 0; --i)
{
X.push_back(S[i]);
}
cout << X << '\n';
}
return 0;
}문제 6
KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.
입력
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
출력
첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.
예제 입력 1
5
6 9 5 7 4
예제 출력 1
0 0 2 2 4
#include <iostream>
#include <stack>
using namespace std;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
stack<pair<int, int> > s;
int num, height;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> height;
while (!s.empty()) {
//수신탑 찾음
if (height < s.top().second) { // s.top().second
cout << s.top().first << " ";
break;
}
//수신탑 찾을 때까지 pop
s.pop();
}
//수신 탑이 없다면
if (s.empty()) {
cout << 0 << " ";
}
//현재 높이를 스택에 푸쉬
s.push(make_pair(i + 1, height));
}
return 0;
}
문제 7
A, B, C로만 이루어졌고 길이가 |S|인 문자열 S가 있다. 당신은 이 문자열에 다음과 같은 시행을 할 수 있다.
- A와 그 뒤에 있는 B를 지운다.
- B와 그 뒤에 있는 C를 지운다.
각 문자는 최대 한 번만 지울 수 있다.
예를 들어 ABCBA를 보자. 각 문자에 왼쪽부터 1번, 2번, 3번. . . 과 같이 번호를 붙이면 다음과 같이 시행할 수 있다.
- 1번 A와 2번 B를 지운다. 이 경우 시행의 횟수는 1번이고, 남은 문자열은 CBA이다. 어떤 두 문자를 골라도 시행의 조건을 만족시킬 수 없으므로, 더 이상 시행을 할 수 없다.
- 1번 A와 4번 B를 지우고, 이어 2번 B와 3번 C를 지운다. 이 경우 시행의 횟수는 2번이고 남은 문자열은 A이다. 문자열에 남은 문자가 하나이므로, 더 이상 시행을 할 수 없다.
이외에도 시행을 할 수 있는 여러 경우의 수가 있다.
시행을 할 수 있는 최대 횟수를 구해라.
입력
첫 번째 줄에 문자열 S가 주어진다.
출력
첫 번째 줄에 답을 출력한다.
제한
- 1 ≤ |S| ≤ 300 000
- S의 모든 문자는 A, B, C 중 하나이다.
서브태스크
| 1 | 5 | S의 모든 문자는 A, B 중 하나이다. |
| 2 | 20 | |S| ≤ 300. |
| 3 | 32 | |S| ≤ 1 000. |
| 4 | 43 | 추가 제약 조건 없음. |
예제 입력 1
ABCBA
예제 출력 1
2
예제 입력 2
ABCBBACBABB
예제 출력 2
5
#include <iostream>
#include <queue>
using namespace std;
bool check[300000];
int cnt, tot;
string str;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> str;
queue<int> q;
// BC 중복 제거
for (int i = 0; i < str.length(); i++)
{
if (str[i] == 'B') // B가 포함되어 있다면 푸시
q.push(i);
else if (str[i] == 'C' && !q.empty())
{
check[q.front()] = 1;
q.pop();
cnt++;
}
}
// AB 중복제거
queue<int> q;
for (int i = 0; i < str.length(); i++)
{
if (str[i] == 'A') tot++;
else if (str[i] == 'B' && tot && !check[i])
{
check[i] = true;
tot--;
cnt++;
}
}
cout << cnt;
}'코테 스터디' 카테고리의 다른 글
| BOJ 2178 BFS 최단거리 찾기 (0) | 2024.08.08 |
|---|
