글 읽기 - 스티커문제 java 시간초과!!

linear114 4년 전 0

인터넷 봐가면서 어쨋거나 속도 줄일 수 있는 방법은 다 써봤는데 시간초과 뜨네요 ㅠㅠ

여기에서 시간초과 요인이 뭐가 있을까요??

이런 것 의미없다고는 하시지만.. 99%에서 시간초과 뜨더라고요 ㅋㅋㅋ;;

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int[] up;
	static int[] down;

	static int[][] d;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(br.readLine());
			up = new int[n + 1];
			down = new int[n + 1];
			
			StringTokenizer preUp = new StringTokenizer(br.readLine());
			StringTokenizer preDown = new StringTokenizer(br.readLine());
			
			for (int j = 1; j <= n; j++) {
				up[j] = Integer.parseInt(preUp.nextToken());
			}
			for (int j = 1; j <= n; j++) {
				down[j] = Integer.parseInt(preDown.nextToken());
			}

			d = new int[n + 1][3];
			bw.write(Integer.toString(maxInArray(simulation(n))) + "\n");
		}
		bw.flush();
		bw.close();
	}

	public static int[] simulation(int n) {
		if (n == 1) {
			d[1][0] = 0;
			d[1][1] = down[1];
			d[1][2] = up[1];
			return d[n];
		}
		if (d[n][0] > 0 && d[n][1] > 0 && d[n][2] > 0) {
			return d[n];
		} else {
			d[n][0] = maxInThreeInteger(simulation(n - 1)[0], simulation(n - 1)[1], simulation(n - 1)[2]);
			d[n][1] = maxInThreeInteger(simulation(n - 1)[0], simulation(n - 1)[2], 0) + down[n];
			d[n][2] = maxInThreeInteger(simulation(n - 1)[0], simulation(n - 1)[1], 0) + up[n];
			return d[n];
		}
	}

	public static int maxInArray(int[] array) {
		int max = array[0];
		for (int i = 0; i < array.length; i++) {
			if (array[i] > max) {
				max = array[i];
			}
		}
		return max;
	}

	public static int maxInThreeInteger(int n1, int n2, int n3) {
		int max = n1;
		if (max < n2) {
			max = n2;
		}
		if (max < n3) {
			max = n3;
		}
		return max;
	}
}

djm03178 4년 전 0

바로 아래 질문에 답이 있습니다.

https://www.acmicpc.net/board/view/36365

linear114 4년 전 0

질문과 답변을 보았는데, 전 스티커 가격을 모두 0으로 둬도 메모이제이션 과정에서 오류가 생기지 않습니다.

djm03178 4년 전 3

당연히 오류는 생기지 않습니다. 오류가 생겼다면 시간 초과가 뜨지 않고 런타임 에러가 났을 테니까요.

중요한 것은 "메모이제이션이 동작하지 않았다"라는 부분입니다. 이게 무슨 의미인지 잘 생각해 보세요. 좀 더 힌트를 드리자면, d[n][0], d[n][1], d[n][2]가 이미 전에 다 계산된 적이 있는데도 if (d[n][0] > 0 && d[n][1] > 0 && d[n][2] > 0) 가 거짓이 되었다는 뜻입니다.

linear114 4년 전 0

흠 다시 생각을 해볼게요! 친절한 답변 너무 감사합니다. 꼭 해결해서 답글 남기겠습니다.

linear114 4년 전 1

djm03178님 정말 감사합니다!

메모이제이션이 동작하지 않았던 이유는

첨부한 코드의 2~7번줄에 있었던 것이네요!

d[1][0]의 값을 0으로 주었고,

d[1][1] 과 d[1][2]의 값도 0이 될 가능성이 있으므로

8~9번쨰의 조건문에 0보다 클 때만 리턴한다는 조건때문에

이 값들이 return이 안될 가능성이 생기고

따라서 무조건 n=1 일때의 과정을 거쳐야하는

11~13줄의 식이 어떠한 경우에서는 값을 받아올 수가 없는거군요!

정말 감사합니다!

덕분에 코드 수정하고 해결했습니다.

많이 배워갑니다.

public static int[] simulation(int n) {
		if (n == 1) {
			d[1][0] = 0;
			d[1][1] = down[1];
			d[1][2] = up[1];
			return d[n];
		}
		if (d[n][0] > 0 && d[n][1] > 0 && d[n][2] > 0) {
			return d[n];
		} else {
			d[n][0] = maxInThreeInteger(simulation(n - 1)[0], simulation(n - 1)[1], simulation(n - 1)[2]);
			d[n][1] = maxInThreeInteger(simulation(n - 1)[0], simulation(n - 1)[2], 0) + down[n];
			d[n][2] = maxInThreeInteger(simulation(n - 1)[0], simulation(n - 1)[1], 0) + up[n];
			return d[n];
		}
	}

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

문제

문제

출처

ICPC

스티커문제 java 시간초과!!

linear114 4년 전 0

djm03178 4년 전 0

linear114 4년 전 0

djm03178 4년 전 3

linear114 4년 전 0

linear114 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말