링크 : https://www.acmicpc.net/problem/14454 어떤 문자열 S에 대해 그 문자열을 오른쪽으로 한 칸 민 문자열을 원래 문자열 S 뒤에 덧붙여 2배로 긴 새로운 문자열로 만드는 연산을 F라고 하자. 첫 문자열 S가 주어지고 여기에 F를 무한 반복해서 나오는 어떤 문자열이 있다고 했을 때, 그 문자열에서 n번째 위치에 어떤 문자가 들어갈 지를 구하는 문제다. 얼핏 생각하면 좀 까다로울 수 있는데, n번째 위치를 크게 나눠서 생각하면, 원래 문자열 s에 F를 쭉 반복해서 붙인 문자열 중 길이가 n보다 작으면서 가장 긴 걸 K라고 하자. 그러면 n번째 위치는 K를 오른쪽으로 한칸 민 문자열에서 n - (K의 길이) 위치에 있는 문자가 된다. 그러면 여기서 거꾸로 돌아가 n번째 위치..
링크 : https://www.acmicpc.net/problem/14777 그다지 어려운 문제가 아니었는데 문제 해석이 잘 안 돼서 한참 끙끙댔다. n개의 도시가 있고 첫 도시에서 시작해서 pi시간에 어떤 도시에 있을 수 있으면 그 도시에서 수여하는 상을 받을 수 있고, n개 도시 각각에 대해 움직이는데 걸리는 시간이 주어졌을 때 최대한 받을 수 있는 상 개수를 구하는게 문제다. 처음에 도시 개수 * 최대 시간 으로 모든 도시 왔다갔다하는거 다 계산하는 DP를 생각했는데 이러면 최대 시간 범위가 100만이라 시간 초과가 난다. 좀 더 생각하면 줄일 수 있는데, 각 도시에 대해 그냥 그 도시에서 수여하는 상 받을 지 아닐 지만 고민하면 되고, 이건 어떤 도시에 p[i]보다 일찍 도착한 다음 p[i]까지 ..