PS 이야기

문제 링크B. Comma Sprinkler길이가 최대 1,000,000인 문장들이 주어진다. 어떤 단어 앞에 콤마(,)가 오면 같은 단어 앞에 모두 콤마가 오도록 바꾸며, 어떤 단어 뒤에 콤마가 올 경우 같은 단어 뒤에 모두 콤마가 오도록 바꿔야한다. 단, 단어의 끝과 시작에서 부자연스럽게 콤마를 추가하진 않는다. 이 때, 최종 문장을 구하는 문제다.같은 단어들을 묶어 정점으로 만든다. 그리고 정점을 단어 앞에 콤마가 오는 경우, 단어 뒤에..

문제 링크D. Happy Number문제에 적혀 있는 함수 $f$가 있다. $f(f(f(...f(n))))$을 했을 때, 1이 되는지를 구하는 문제다.입력으로 주어지는 수는 최대 1,000,000,000인데, 큰 수가 주어진다하더라도 $f(n)$의 결과값은 작다. 때문에 이 문제는 함수 $f$를 구현하고 결과값이 1이 되는지만 확인하는 간단한 문제가 된다.#include <bits/stdc++.h> using namespace std; ..

문제 링크I. Robot로봇은 초기에 동쪽을 바라보고 있고, $(0, 0)$ 위치에 있다. 회전하는 명령과 앞으로 이동하는 명령이 주어졌을 때, 주어진 정사각형 범위를 벗어나는지 아닌지 확인하고 벗어나지 않으면 최종 위치를 출력하는 문제다.단순한 구현 문제이므로 설명은 생략한다.#include <bits/stdc++.h> using namespace std; int yy[] = {0, -1, 0, 1}, xx[] = {1, 0,..

문제 링크 I. Q-Index $n$개의 논문들에 대한 인용횟수가 주어지고, $k$번 이상 인용된 $k$편의 논문이 있고, 나머지 $n-k$편의 논문은 모두 인용횟수가 $k$이하일 때, Q-Index는 $k$라고 얘기한다. 가능한 Q-Index 중 가장 큰 값을 구하는 문제다. 매우 쉬운 문제라 0이상 $n$이하의 $k$를 정한 뒤, 실제로 $k$가 Q-Index가 되는지 확인하는 $O(n^2)$ 방법과 인용횟수 배열을 내림차순으로 정렬한 ..

문제 링크 E. 닉네임에 갓 붙이기 $N$개의 닉네임이 음절 단위로 쪼개져 주어진다. 첫 음절을 제외하고, 맨 앞에 "god"을 붙여 출력하는 문제다. 줄 별로 입력받고 입력 받은 문자열을 공백으로 나누어 문자열 배열로 만들어주면 된다. C, C++에서 이는 strtok 함수를 통해 간단히 해결할 수 있다. #include <bits/stdc++.h> using namespace std; int T; char buf[999]; int..

문제 링크 C. Ceiling Function $K$개의 노드로 구성된 Binary Search Tree가 $N$개 주어진다. 이 때 서로 다른 모양을 갖는 BST의 개수를 구하는 문제다. 구조체를 써서 BST를 구현하고 두 노드에 대해 각 노드를 루트로한 서브트리가 같은지 비교해주는 재귀 함수를 구현하여 쉽게 해결할 수 있다. #include <bits/stdc++.h> using namespace std; int N, M;..

문제 링크E. Association for Computing MachineryN개의 문제가 있는 ICPC 세트가 있다. 각 문제별로 푸는 시간이 주어진다. p번 문제의 First Solve 상을 노려야하기 때문에 p번 문제를 제일 먼저 풀고 제일 좋은 전략으로 문제를 해결할 때, 푼 문제 수와 패널티를 구하는 문제다. 문제는 한 번에 맞는다고 가정한다.p번 문제를 0번지에 놓고 1번지부터 이후를 푸는 시간순서로 정렬한 다음에 순서대로 시간이 300분..

문제 링크L. Wheel of Numbers숫자 N개가 적힌 원판이 있다. 원판에 다트를 던져 한 곳을 맞춘다. 그 다트를 기준으로 시계방향으로 숫자 M개를 읽어 수 Z를 만든다. X ≤ Z ≤ Y 라면 점수를 획득한다. 원판과 X, Y가 주어졌을 때, 점수를 획득하는 경우의 수를 구하는 문제다.아주 간단한 구현 문제다. M ≤ 9이므로, 64bit 정수형을 사용해서 X, Y, Z를 표현할 수 있다.#include <bits/..

문제 링크 A. Awkward Group $N$개의 정점이 간선에 가중치가 있는 완전 그래프가 있다. 정점의 전체 집합 $P$의 부분 집합 $F$가 있다고 했을 때,문제에 적힌 조건을 만족하는 $F$의 개수를 구하는 문제다. 초기에 간선이 전혀 없는 그래프를 생각하자. 가중치가 작은 간선들부터 차례로 추가해나간다. 간선 하나를 추가할 때마다 그 간선이 속한 연결 요소(connected component)가 완전 그..

문제 링크 A. Amalgamated Artichokes 1부터 N까지 정수 k가 있을 때, price(k) 에 대해 최대 감소폭을 구하는 문제다. 이전까지 나온 최대 값을 저장해두고 현재 값이 최대값 보다 같거나 작다면 최대 감소폭에 차이를 갱신해주고, 현재 값이 최대값 보다 크다면 최대값을 갱신해주면 된다. 시간복잡도는 $O(N)$이다. #include <bits/stdc++.h> using namespace std; int P, A..