PS 이야기

호텔에 온 손님들은 101호 부터 시작하여 201호, 301호, ..., H층 1호에 배정 되며, 그 이후에는 102호, 202호, ..., H층 2호에 배정된다. 시간복잡도 O(HW) 만에 계산을 하여도 되지만, 규칙을 잘 살펴보면 한 번에 N 번째 손님이 배정 받는 방 번호를 알 수 있다. #include int T,H,W,N; int main() { for (scanf("%d",&T);T--;){ scanf("%d%d%d",&H,&W,&N); printf("%d%02d\n",(N-1)%H+1,(N-1)/H+1); } }

한글 문제임에도 불구하고 문제를 이해하기가 다소 까다로운 편이다. 이 문제는 DP로 해결할 수 있다. 가능한 상황은 $2^N \times 2^M$ 가지가 있다. 이는 최대 $2^{40}$ 가지로 경우의 수가 꽤 많다. 가능한 경우를 줄이도록 생각해야한다. 현재 상황에서 문제별로 채점이 되었는지, 아직 채점이 되지 않았는지 경우는 총 $2^M$가지가 있다. 그 중 한 상황에서 여태까지 살아남은 사람은 필요충분으로 여태까지 채점된 문제들에 대해서 모두 Yes라고 대답한 사람이다. 따라서, 어떤 문제들을 채점했는지를 알면, 살아남은 사람 또한 알 수 있게 된다. 따라서, DP를 $2^M$ 가지 경우에 대해서 돌리면 된다. #include #include using namespace std; const int ..

Suffix Array (접미사 배열) Suffix Array(韓: 접미사 배열)은 어떤 문자열의 suffix(접미사)들을 사전순으로 나열한 배열을 의미한다. 문자열 관련된 문제에서 자주 쓰이는 방법이다. 예를 들어, 문자열 $S = banana$가 있다고 하자. 문자열 $S$의 접미사들은 아래와 같다. suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 문자열 $S$의 접미사 배열은 아래와 같다. suffixia6ana4anana2banana1na5nana3 접미사 배열에서 문자열을 배열로 가지고 있으면 공간복잡도가 $O(N^2)$이기 때문에 접미사를 나타내는 정수 $i$를 가지고 있는다. 즉, "banana"의 접미사 배열은 [6,4,2,1,5,3] 이다. 접미사 배..