글 읽기 - 런타임에러... 코드 확인 부탁드립니다...

tjtjdgur34 6년 전 0

런타임 에러가 계속 뜨네요 ㅜ 코드 확인 부탁드립니다.

import java.util.Scanner;

public class Main {
	static long[] top = new long[500001];
	static long[] receive;
	static long[][] map;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long n = scan.nextLong();
		long mtop = 0;
		for(int i = 1; i <= n; i++) {
			top[i] = scan.nextLong();
			if(mtop < top[i])
				mtop = top[i];
		}
		
		receive = new long[(int) (n+1)];	
		map = new long[(int) (n+1)][(int) (mtop+1)];
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= mtop; j++) {
				if(j <= top[i])	map[i][j] = 1;
				else map[i][j] = 0;
			}
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = i-1; j >= 0; j--) {
				if(map[j][(int) top[i]] == 1) {
					receive[i] = j;
					break;
				}
			}
		}
		
		for(int i = 1; i <= n; i++) {
			System.out.print(receive[i] + " ");
		}
	}

}

kdk8361 6년 전 1

n 최대치 50만, 탑 높이 최대치 1억이라 n*top 사이즈로 배열 만드시면 터집니다.

@kdk8361 안녕하세요! 조언 감사드립니다! 혹시, 질문 하나만 더 드려도 괜찮을까요? 다름이 아니라... 대부분 문제를 푸시는 분들을 보면, 코딩 전 시간복잡도를 고려하셔서 이 방법은 쓰면 안되겠다 혹은 이 방법을 이용하면 풀리겠다. 를 결정하시던데... 저는 아직 이 부분이 많이 부족한 것 같습니다. 혹시 방법이라던지 학습 방법 같은 것을 여쭤 봐도 괜찮을까요? 감사합니다.^^

kdk8361 6년 전 1

가장 중요한 점은 알고리즘 자체를 이해하는 것과 경험이라고 생각합니다. 학습 방법은 이런 온라인 저지 커뮤니티나 고수분들이 운영하시는 문제 해설 블로그에서 해당문제를 찾으시고 문제별로 궁금한점을 물어보시면서 차근차근 경험을 쌓는게 좋을 것 같습니다. 저도 이 부분은 많이 부족해서 다른분들에게도 여쭤보는게 좋을 것 같습니다.

simm4256 6년 전 1

빅오표기법으로 시간복잡도를 나타내는게 익숙치 않다면

먼저 알고리즘이 떠오르셨다면, 문제 조건상 최악의 경우에는 몇 번의 연산이 필요한지(혹은 얼마만큼의 메모리가 필요한지) 계산기를 두드려보세요.

예를 들어

https://www.acmicpc.net/proble...

문제의 경우

만약 맵 크기만큼의 2중 배열을 만들어서 한 칸씩 처리하려고 할 경우

최악의 경우는 L이 1e8인 경우겠죠?

그럼 배열을 (1e8)^2 개를 만들어야겠네요.

당연히 메모리 초과가 날 것입니다. 따라서 다른 해결법을 찾아야 합니다.

시간 초과도 비슷한 방식으로 생각해보세요.

대충 1억번의 연산을 1초로 놓고 시간제한과 비교해보시면 됩니다.

이게 익숙해지면 자연히 어떤 알고리즘의 시간복잡도를 빅오표기법으로 표현할 능력이 생길 겁니다.

tjtjdgur34 6년 전 0

@kdk8361 @simm4256 좋은 답변 감사드립니다. 혼자 알고리즘 공부하는데 있어 힘든 점이 많지만 덕분에 많은 것을 배워가는 것 같습니다. 감사합니다!

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

문제

문제

출처

ICPC

런타임에러... 코드 확인 부탁드립니다...

tjtjdgur34 6년 전 0

kdk8361 6년 전 1

tjtjdgur34 6년 전 0

kdk8361 6년 전 1

simm4256 6년 전 1

tjtjdgur34 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말