글 읽기 - 농부 후안은 바리스타입니다 시간초과 문제

didgmldud0 6년 전 0

뭔가 문제인거죠,..,?

시간초과라는데..

import java.util.Scanner;

public class Main{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        String NMQ = sc.nextLine();
        
        int N = Integer.parseInt(NMQ.split(" ")[0]);
        int M = Integer.parseInt(NMQ.split(" ")[1]);
        int Q = Integer.parseInt(NMQ.split(" ")[2]);
        
        int[][] area= new int[N][M];
        
        for(int i=0; i<Q; i++)
        {
        	String[] execu = sc.nextLine().split(" ");
        	if(execu[0].equals("1"))
        	{
        		int srow= Integer.parseInt(execu[1])-1;
        		int erow= Integer.parseInt(execu[3]);
        		int scolumn= Integer.parseInt(execu[2])-1;
        		int ecolumn= Integer.parseInt(execu[4]);
        		int seed= Integer.parseInt(execu[5]);
        		for(int r=srow; r<erow; r++)
        		{
        			for(int c=scolumn; c<ecolumn; c++)
            		{
            			area[r][c]=seed;
            		}
        		}
        	}
        	else if(execu[0].equals("2"))
        	{
        		int x= Integer.parseInt(execu[1])-1;
        		int y= Integer.parseInt(execu[2])-1;
        		System.out.println(area[x][y]);
        	}
        }
        
    }
}

jung2381187 6년 전 1

5000 x 5000짜리 농장 전체에 씨앗 심기를 200000번 하는 걸 이렇게 노가다로 계산하면 시간 초과가 날 수 밖에 없습니다.

더 빠른 계산법이 필요합니다.

jh05013 6년 전 0

https://www.acmicpc.net/board/...
"질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요."

bupjae 6년 전 1

이 프로그램의 시간복잡도는 O(NMQ) 입니다.

최대 크기의 입력 데이터의 경우 약 5000 * 5000 * 200000 = 5조 만큼의 연산이 필요한데, 당연히 시간 초과가 날 수 밖에 없습니다.

didgmldud0 6년 전 0

와우 그래서 맥스 데이타가 있었군요..

감사합니다 !!!

totoyang 6년 전 0

저도 같은 문제를 경험중입니다.

처음에 2-D 벡터에 해당 Cell별로 씨앗을 뿌리다가 시간초과가 나길래 이건 아니다 싶어서

문제를 다시 살펴보니.

문제에서 답을 구하라고 하는 것은 특정 Cell에 있는 Net(씨앗)이기 때문에 전체 농장Cell을 업댓할 필요가 없다고 생각했습니다.

그래서 다시 전략을 바꾸어서

씨앗을 뿌리는 위치 (왼쪽 하단과 오른쪽 상단) Point 좌표 정보와 그때의 d(씨앗개수)를 저장했고,

씨앗의 위치를 구할떄마다 위치 판정을 통해 Net(씨앗)을 계산했습니다.

그런데 신기한것은 이렇게 했음에도 시간초과 판정이 뜬다는 것입니다.

입출력 시간이 잘못되었나 싶어서 개인적으로 입출력 코드를 모두 C언어의 scanf(), prinf()로 바꾸었는데도 그러네요..

혹시 해결하시게 되면 도움좀 구합니다.

아래는 저의 실패한 코드 입니다.

#include <iostream>

int pxLeft[200001], pyButtomm[200001], pxRight[200001], pyUp[200001], pd[200001];

int main() {

	freopen("input.txt", "r", stdin);

	int N, M, Q;
	scanf("%d %d %d\n", &N, &M, &Q);

	int index = 0;
	for (int i = 0; i < Q; ++i) {
		char first;
		scanf("%c ", &first);
		if (first == '1')
		{
			int xLeft, xRight, yButtom, yUp, d;
			
			scanf("%d %d %d %d %d\n", &xLeft, &yButtom, &xRight, &yUp, &d);
			
			pxLeft[index] = xLeft;
			pyButtomm[index] = yButtom;
			pxRight[index] = xRight;
			pyUp[index] = yUp;
			pd[index] = d;
			index += 1;
		}
		else
		{
			int x, y;
			scanf("%d %d\n", &x, &y);

			long long answer = 0;
			int cnt = 0;
			while(pxLeft[cnt])
			{
				if (pxLeft[cnt]<= x && x <= pxRight[cnt]
					&&pyButtomm[cnt]<= y && y <= pyUp[cnt])
				{
					answer += pd[cnt];
				}
				++cnt;
			}

			printf("%lld\n", answer);
		}
	}


	return 0;
}

jh05013 6년 전 0

그렇게 해도 시간복잡도가 큽니다. 각 쿼리가 10만 개씩 들어온다고 생각해 보세요.

이번에 추가된 바리스타 시리즈 모두 이렇게 간단하게 풀리지 않습니다.

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

문제

문제

출처

ICPC

농부 후안은 바리스타입니다 시간초과 문제

didgmldud0 6년 전 0

jung2381187 6년 전 1

jh05013 6년 전 0

bupjae 6년 전 1

didgmldud0 6년 전 0

totoyang 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말