PS 이야기

1. 비트문자열 특정 규칙으로 만들어지는 길이 $2^i$인 이진문자열 $S_i$가 있다. 구간 $[s, e]$가 있을 때, $S_i$의 $s$ 번째 문자부터 $e$ 번째 문자까지 문자 중에서 1의 개수를 구하는 문제다. 단, 하나의 입력 파일에 최대 20만 개의 테스트 케이스가 들어올 수 있어서 상당히 빠른 시간 안에 문제를 해결해야 한다. 문제 설명에 적힌 규칙과 다른 방식으로 $S_i$를 설명할 수 있다. $S_0$는 "0"이며, $1$ 이상인 $i$에 대해 $S_i$는 $S_{i-1}$에서 0/1을 뒤집은 것과 $S_{i-1}$을 이어 붙인 문자열이 된다. 즉, $S_1$은 "10"이며, $S_2$는 "10"에서 0/1을 뒤집은 "01"에 "10"을 이어 붙인 "0110"이 된다. $S_3$은 "0..

1. 사진작가 정수로 이루어진 길이 $N$인 배열 $A$가 주어진다. 이 배열의 부분배열 중에서 같은 수를 여러 개 포함하고 있지 않은 부분배열이 있다. 그러한 부분배열 중에서 길이가 가장 큰 부분배열의 길이를 구하는 문제다. 배열을 구성하는 정수의 범위가 $1$ 이상 $1\,000\,000$ 이하이다. 크기가 $1\,000\,000$인 배열을 하나 잡아서 마지막으로 그 수가 등장한 인덱스를 저장하면, 어떤 수 $i$에 대해, $A_i$랑 같은 수 중 왼쪽에 있으면서 가장 오른쪽에 있는 수의 인덱스 $last_i$를 구할 수 있다. 그다음, 오른쪽 끝이 $i$인 부분배열 중에서 문제의 조건을 만족하는 가장 큰 부분배열의 왼쪽 끝은 $\max\limits_{1 \le j \le i}(last_i)+1$이..

오랜만에 풀이 및 후기 글을 적는다. Google Code Jam은 매년 꾸준히 참가해왔다. 그동안 PS 공부할 시간적 여유가 없어서, 참가만 해왔었고, 다행히 최근에는 육아휴직으로 시간이 생겨서 밀린 PS 공부를 했다. 주로 최근에 well-known이 된 알고리즘/자료구조들을 공부하고 익히는 시간이었다. 다만, 최근 Round 2 성적이 최근에 공부한 것을 감안했을 때 아쉬움이 많이 남는 결과라 현재 심경과 풀이를 정리할 겸 포스팅을 시작한다. A. Spiraling Into Control Spiral 모양의 $N \times N$ 크기의 행렬이 있을 때, 원하는 만큼 shortcut을 놓아 정확히 $K$ 번의 이동으로 출발점 $1$에서 도착점 $N^2$으로 가는 문제다. Shortcut이 하나도 없..

1. 계단 $1$ 층부터 $M$ 층까지 총 $M$ 개의 층이 있는 건물이 있다. 건물의 $F$ 층에서 시작하여 계단을 통해 한 층을 올라가거나, 엘리베이터를 타고 원하는 층으로 이동할 수 있다. 정확히 $N$ 번 계단을 통해 층을 오르면서 엘리베이터를 적절히 타서 $F$ 층으로 돌아오고 싶다. 이때, 엘리베이터를 타는 횟수의 최솟값을 구하는 문제다. 문제에서 $F$가 입력으로 주어지지만, $F$는 답에 영향을 미치지 않는다는 것을 알 수 있다. 답은 $\left\lceil\frac{N}{M-1}\right\rceil$이다. 더보기 #include using namespace std; int M, F, N; int main() { cin >> M >> F >> N; cout

1. S OR T 스페이스(S)와 탭(T)을 입력한 순서가 주어졌을 때, 총 몇 칸 띄어지게 되었는지 구하는 문제다. 단, 탭 크기는 4다. 문자열을 입력받아서 S가 나오면 칸 수를 1 늘려주고, T가 나오면 칸 수를 현재 칸 수보다 큰 4의 배수로 만들어주면 된다. 더보기 A = input() S = 0 for c in A: S += 1 if c == 'T': while S%4 != 0: S += 1 print(S) 2. 카트라이더 별 모으기 3개의 별이 있고 각 별을 획득할 수 있는 기록 제한이 주어졌을 때, 주어진 기록이 몇 개의 별을 획득할 수 있는지 구하는 문제다. 이 문제에서 시간이 기록은 'aa:bb:cc'꼴로 주어지는데, 이 기록 문자열을 정수로 변환해도 되고, 정수로 변환하지 않고 문자열..

문제 및 채점: 사이트 A. New Elements: Part 1 질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자를 질량 순서대로 정렬하려고 한다. 다만, 분자의 질량은 모두 달라야 한다. 이때, 정렬 결과로 가능한 순서는 모두 몇 개인지 구하는 문제다. 서로 다른 i와 j에 대해, C[i] ≤ C[j], J[i] ≤ J[j]를 만족하면 질량 X, Y와 상관없이 질량의 대소 관계가 명확하다. 다만, C[i] < C[j], J[i] > J[j]와 같이 원소 C 개수의 대소 관계와 원소 J 개수의 대소 관계가 뒤집혀있..

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번 종류 상점에 대해 거리를 나타낸다. 이 순간 좌..

1. 방 배정하기 (room) 수용인원이 A, B, C인 세 종류의 방이 있다. 이 방들을 적절히 예약하여 정확히 N명의 사람이 묵을 수 있도록 하는 문제다. N이 최대 300으로 굉장히 작기 때문에 아래 DP 배열을 정의하고 값을 채우면 된다. D[i] = 정확히 i명의 사람이 묵을 수 있도록 예약할 수 있는가 (있으면 true, 없으면 false) 점화식은 다음과 같다: D[i] = D[i-A] OR D[i-B] OR D[i-C] #include using namespace std; int A, B, C, N; bool D[350]; int main() { cin >> A >> B >> C >> N; D[0] = 1; for (int i=0;i

1. 물통 (bucket) 크기가 A인 물통과 크기가 B인 물통이 있고, 처음에는 모든 물통이 비어있다. 아래 4가지 동작을 통해 크기가 A인 물통에는 P 만큼, 크기가 B인 물통에는 Q 만큼의 물을 담는 최소 동작 횟수를 구하는 문제다. 1) 크기가 A인 물통을 비우거나 가득 채운다. 2) 크기가 B인 물통을 비우거나 가득 채운다. 3) 크기가 A인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 B인 물통이 가득 차면 옮기는 것을 멈춘다. 4) 크기가 B인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 A인 물통이 가득 차면 옮기는 것을 멈춘다. 크기가 A인 물통에 a만큼의 물이, 크기가 B인 물통에 b만큼의 물이 담겨 있는 상태를 (a, b)라고 나타내자. 초기 상태나..

ICC $N$개의 정점으로 이루어진 그래프가 있다. 그래프의 초기 상태에는 간선이 하나만 존재한다. 두 정점 집합 사이에 간선이 있는지 묻는 질문을 통해 간선이 무엇인지 알아낸다. 알아낸 이후에 새로운 간선이 또 추가된다. 항상 싸이클이 생기지 않도록 간선이 주어지며, 이 작업을 총 $N-1$번 수행하고 질문을 가능한 적게해야하는 문제다. 처음 상황, 즉, $N$개의 정점이 있고 그들 사이에 간선이 하나만 있는 상황에서 생각해보자. 우선 간선을 가지고 있는 임의의 두 정점 집합을 최대한 적은 질문안에 찾아야한다. 이는 최대 $\lceil\lg N\rceil - 1$번 질문만에 찾을 수 있다. 바로 각 정점 번호를 0번부터 N-1번까지 나타낼 때, 각 비트에 대해 비트값이 0인 집합과 비트값이 1인 집합 ..