PS 이야기

문제 링크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..

문제 링크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)가 완전 그..