PS 이야기

A. 새 집 (New Home) $N$개의 상점이 주어진다. $i$번째 상점은 위치 $x_i$에 지어지며, 종류는 $t_i$이고, $a_i$년 초에 생겨, $b_i$년 말에 없어진다. 상점의 종류는 $K$가지이다. $Q$개의 질문이 주어진다. $i$번째 질문은, $y_i$년 중순에 $l_i$위치에 집을 지을 경우, 상점 종류마다 제일 가까운 상점과의 거리를 구해 그 중 최대값을 요구한다. 예를 들어, $K=2$이고 어떤 특정 시점에 1번 종류 상점이 좌표 2, 5, 13에 있고, 2번 종류 상점이 좌표 6, 10, 15에 있다고 했을 때, 아래와 같은 그래프를 그릴 수 있다. 그래프에서 파란색 선은 1번 종류 상점에 대한 거리를 나타내고, 주황색 선은 2번 종류 상점에 대해 거리를 나타낸다. 이 순간 좌..

문제 링크 B. Comma Sprinkler 길이가 최대 1,000,000인 문장들이 주어진다. 어떤 단어 앞에 콤마(,)가 오면 같은 단어 앞에 모두 콤마가 오도록 바꾸며, 어떤 단어 뒤에 콤마가 올 경우 같은 단어 뒤에 모두 콤마가 오도록 바꿔야한다. 단, 단어의 끝과 시작에서 부자연스럽게 콤마를 추가하진 않는다. 이 때, 최종 문장을 구하는 문제다. 같은 단어들을 묶어 정점으로 만든다. 그리고 정점을 단어 앞에 콤마가 오는 경우, 단어 뒤에 콤마가 오는 경우를 나타내는 두 정점으로 이원화한다. 단어 앞에 콤마가 오거나, 단어 뒤에 콤마가 오는 경우 해당하는 정점에 색칠은 한 뒤, 원래 문장에서 인접한 두 단어의 정점에는 방향성 간선을 만들어주어 Flood-Fill 한다. 그러면 시간복잡도 $O(V+..

문제 링크 D. Happy Number 문제에 적혀 있는 함수 $f$가 있다. $f(f(f(...f(n))))$을 했을 때, 1이 되는지를 구하는 문제다.입력으로 주어지는 수는 최대 1,000,000,000인데, 큰 수가 주어진다하더라도 $f(n)$의 결과값은 작다. 때문에 이 문제는 함수 $f$를 구현하고 결과값이 1이 되는지만 확인하는 간단한 문제가 된다. #include using namespace std; int N; int main() { set vis; scanf("%d", &N); while (N > 1){ if (vis.count(N)){ puts("UNHAPPY"); return 0; } vis.insert(N); int nxt = 0; for (int v=N;v;v/=10) nxt +=..