글 읽기 - 시간초과 ...어떻게 줄여야할까요

kimsy96 6년 전 0

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

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

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

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

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

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

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

#include <stdio.h>
#include <stdlib.h>



typedef struct _cordinate
{
	int x;
	int y;
}Cor;

Cor arr[100000];
char str[300002];



int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);
	int i,j;

	Cor origin = { 0,0 };
	for (i = 0; i < n; i++)
	{
		scanf("%d %d", &arr[i].x, &arr[i].y);
	}
	scanf("%s",str);
	for(i=0;i<m;i++)
    {
        long long DX=0;
        long long DY=0;
        if(str[i]=='S')
        {
            origin.y+=1;

        }

        else if(str[i]=='J')
            origin.y-=1;
        else if(str[i]=='I')
            origin.x+=1;
        else if(str[i]=='Z')
            origin.x-=1;
        for(j=0;j<n;j++)
        {
            DX+=abs(origin.x-arr[j].x);
            DY+=abs(origin.y-arr[j].y);
        }
        printf("%lld\n",DX+DY);
    }
    return 0;







}

chogahui05 6년 전 1

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

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

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

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

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

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

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

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

chogahui05 6년 전 1

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

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

kimsy96 6년 전 0

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

감사합니다

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

문제

문제

출처

ICPC

시간초과 ...어떻게 줄여야할까요

kimsy96 6년 전 0

chogahui05 6년 전 1

chogahui05 6년 전 1

kimsy96 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말