글 읽기 - 시간초과 나는이유... 도저히 모르겠네요 간단한문제인데 ㅠㅠ

dksxoghl 4년 전 0

자바의 신님들 도와주세요 ㅠㅠ

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

public class Exam1932 {
static int n, sum = 0, max = 0;
static int[][] g;

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
g = new int[501][501];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j <= i; j++) {
g[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0,sum);
System.out.println(max);
}

static void dfs(int x, int y,int sum) {
sum += g[x][y];
if (x == n - 1) {
if (sum > max)
max = sum;
} else {
for (int i = 0; i < 2; i++) {
y += i;
x++;
dfs(x, y,sum);
x--;
}
}
}
}

djm03178 4년 전 0

dfs를 하면 모든 경우의 수를 탐색하게 되는데 이는 지수 시간 복잡도를 가집니다.

질문 게시판에 올라온 다른 질문들을 참고하면서 메모이제이션을 하는 방법에 대해 알아보세요.

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

문제

문제

출처

ICPC

시간초과 나는이유... 도저히 모르겠네요 간단한문제인데 ㅠㅠ

dksxoghl 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말