글 읽기 - 2900번 자바

ylee399 2년 전 0

도저히 안되서 다시 글 남겨요..

이 문제 풀고 다시 하는데 시간초과가 나서

loop 하나라도 줄이면 될까 싶어서 main에 주석처리 한 부분을 something() 안에 넣고 해봤는데

시간초과가 나오진 않고 틀렸습니다가 나오네요..

입력 받는것만 BufferedReader쓰고 출력은 그냥 했어요

반례가 있는걸까요 아니면 코드 자체가 틀린걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _2900 {

	static int[] array = new int[1000000];
	static int[] prefixSum = new int[1000000];
	static int N = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String firstLine = br.readLine();
		
		N = Integer.parseInt(firstLine.split(" ")[0]);

		int numJumps = Integer.parseInt(firstLine.split(" ")[1]);

		String[] jumps = br.readLine().split(" ");
		for (int i = 0; i < numJumps; i++) {
			something(Integer.parseInt(jumps[i]));
		}

//		for(int i = 0; i<N; i++) {
//			if (i == 0) {
//				prefixSum[0] = array[0];
//			} else {
//				prefixSum[i] = prefixSum[i - 1] + array[i];
//			}
//		}
        
		int tc = Integer.parseInt(br.readLine());

		for (int i = 0; i < tc; i++) {
			String[] eachCase = br.readLine().split(" ");
			int start = Integer.parseInt(eachCase[0]);
			int end = Integer.parseInt(eachCase[1]);
			int sum = 0;

			if (start == end) {
				sum = array[start];
			} else if (start == 0) {
				sum = prefixSum[end];
			} else {
				sum = prefixSum[end] - prefixSum[start - 1];
			}
			System.out.println(sum);
		}

	}

	static void something(int jump) {
		int i = 0;
		while (i < N) {
			array[i] = array[i] + 1;
			if (i == 0) {
				prefixSum[0] = array[0];
			} else {
				prefixSum[i] = prefixSum[i - 1] + array[i];
			}
			i = i + jump;
		}
	}
}

jh05013 2년 전 1

이러면 prefixSum이 제대로 계산되지 않습니다. prefixSum[i]만 바뀌는데 실제로는 전부 바꿔야 하기 때문입니다.

ylee399 2년 전 0

@jh05013

이런식으로 하면 시간초과가 나는데 시간을 줄일 방법이 있을까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _2900 {

	static int[] array = new int[1000000];
	static int[] prefixSum = new int[1000000];
	static int N = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String firstLine = br.readLine();
		
		N = Integer.parseInt(firstLine.split(" ")[0]);

		int numJumps = Integer.parseInt(firstLine.split(" ")[1]);

		String[] jumps = br.readLine().split(" ");
		for (int i = 0; i < numJumps; i++) {
			something(Integer.parseInt(jumps[i]));
		}

		for(int i = 0; i<N; i++) {
			if (i == 0) {
				prefixSum[0] = array[0];
			} else {
				prefixSum[i] = prefixSum[i - 1] + array[i];
			}
		}
        
		int tc = Integer.parseInt(br.readLine());

		for (int i = 0; i < tc; i++) {
			String[] eachCase = br.readLine().split(" ");
			int start = Integer.parseInt(eachCase[0]);
			int end = Integer.parseInt(eachCase[1]);
			int sum = 0;

			if (start == end) {
				sum = array[start];
			} else if (start == 0) {
				sum = prefixSum[end];
			} else {
				sum = prefixSum[end] - prefixSum[start - 1];
			}
			System.out.println(sum);
		}

	}

	static void something(int jump) {
		int i = 0;
		while (i < N) {
			array[i] = array[i] + 1;
			i = i + jump;
		}
	}
}

jseo 2년 전 0

주어지는 jump 값이 전부 1인 경우를 생각해보세요. 총 수행시간은 O(N * numJumps) 가 될겁니다.

하지만 굳이 jump = 1 케이스마다 something을 호출할 필요가 있을까요?

예를 들어서 jump = 1인 입력이 k개라고 하면, something(1) 함수를 한번만 호출하고 array[i] = array[i] + k를 하면 시간을 훨씬 단축 시킬수 있겠죠.

jump = 2, 3, ... N인 입력도 마찬가지구요.

그리고 이러한 식으로만 해도 꽤 효율적이라는건 제가 전에 답변한 식으로 증명 할 수 있습니다.

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

문제

문제

출처

ICPC

2900번 자바

ylee399 2년 전 0

jh05013 2년 전 1

ylee399 2년 전 0

jseo 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말