kimsy96   1년 전

처음에 문제를 풀었을 때 아예 문제를 잘못이해해서 부랴부랴 다시 풀었습니다.

대충 문제의 입출력 조건대로 나오고 논리도 맞는거같아서 제출했는데 시간초과가 발생했습니다.

대충 시간복잡도를 계산해보니 시간초과가 날만하더군요..

그런데 아무리 고민해봐도 이 코드의 시간복잡도를 줄이는 방법이 잘 안떠오르네요 .

조금 도와주셨으면 합니다.

좌표를 받을 구조체를 선언한 다음 배열 선언을 하였고, 명령 입력을 받을 char 배열을 선언한다음

char 배열의 각 성분을 조사하며 기준좌표 값을 변화시켰습니다.

chogahui05   1년 전

이미 누적합에 대한 정보를 알고 있다면. Q마다 n번만큼 돌면서 계산할 필요가 없습니다.

현재 상근 로봇의 위치를 (x_cur,y_cur)라고 한다면

x가 x_cur보다 크거나 같은 경우와 (#)

작은 경우로 나눠서 x축으로의 이동 거리의 합을 구하고요.


y가 y_cur보다 크거나 같은 경우와 (#)

작은 경우로 나눠서 y축으로의 이동 거리 합을 구합니다.


그러면 이 (#)은 어떻게 구할까요? lower_bound로 구하시면 됩니다.

나머지 부분까지 알려드리면 재미 없어요.

chogahui05   1년 전

솔직히 제가 c++의 STL을 쓰기 전에는 qsort 써가면서..

구현했는데요. 지금 이 문제를 풀어라 한다면. 그냥 STL 써서 구현하는 게 속 편할 거 같네요.. ㅎㅎ

kimsy96   1년 전

음.. 일단 한번 고민해보겠습니다.

감사합니다

댓글을 작성하려면 로그인해야 합니다.