글 읽기 - 9184번 문제에서 계속 시간 초과가 뜹니다. 도와주세요.

kgy0713 1년 전 0

배열을 만들어서 그 배열에 이미 계산된 값들을 넣어놓고, 이미 계산된 값들이 있는지 확인하는 작업을 가장 먼저 하게끔 코드를 짠 거 같은데도 시간초과가 계속 나옵니다. 다른 분들이 작성하신 코드들을 찾아봐도 제가 작성한 것과 별반 차이가 없는 거 같은데 혹시 제가 무언가 놓치는 게 있는 건가요? 감사합니다.

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

public class Main {
	
	public static int[][][] answers = new int [21][21][21];  // 0부터 20까지
	
	// 들어오는 a, b, c 값이 20을 넘어가거나 0보다 작을 수도 있음
	public static boolean checkRange(int a, int b, int c) {
		return a >= 0 && a <= 20 && b >= 0 && b <= 20 && c >= 0 && c >= 20;
	}
	
    // W함수
	public static int w(int a, int b, int c) {
		if (checkRange(a, b, c) && answers[a][b][c] != 0) {  // 이미 계산된거는 넘어간다
			return answers[a][b][c];
		}
		
		if (a <= 0 || b <= 0 || c <= 0) {
			return 1;
		}
		
		if (a > 20 || b > 20 || c > 20) {
			return answers[20][20][20] = w(20, 20, 20);
		}
		
		if (a < b && b < c) {
			return answers[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
		} else {
			return answers[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			if (a == -1 && b == -1 && c == -1) {
				break;
			}
			
			sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(w(a, b, c)).append("\n");
		}
		
		System.out.println(sb);
	}

}

djm03178 1년 전 0

checkRange 함수 내에 오타가 있습니다.

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

문제

문제

출처

ICPC

9184번 문제에서 계속 시간 초과가 뜹니다. 도와주세요.

kgy0713 1년 전 0

djm03178 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말