글 읽기 - 1520 내리막길 시간초과나요 ㅠㅠ

yul2yull 8년 전 0

채점 되다가 시간초과로 나와요 ㅠㅠㅠ

고수님들 도와주세요 ~~!!

import java.util.Scanner;

public class Main {
	static int n; // 가로
	static int m; // 세로
	static int[][] map = new int [501][501];
	static int[][] arr = new int [501][501];
	static int[][] p = {{1,0},{-1,0},{0,1},{0,-1}};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				map[i][j]=-1;
			}
		}
		System.out.println(checkF(1, 1));
	}
	
	public static int checkF(int x, int y){
		if (x == n && y == m) {
			return 1;
		}
		if (map[x][y]!=-1) {
			return map[x][y];
		}
		int tmp = 0;
		for (int k = 0; k < 4; k++) {
			int px = x + p[k][0];
			int py = y + p[k][1];
			if (px>0 && py>0 && px<=n && py<=m && arr[x][y]>arr[px][py]) {
				tmp += checkF(px,py);
			}
		}
		return tmp;
	}
}

ckdgus2482 8년 전 0

메모이제이션이 제대로 안되어있는데요...

tmp리턴하기전에 map에 넣으세요.

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

문제

문제

출처

ICPC

1520 내리막길 시간초과나요 ㅠㅠ

yul2yull 8년 전 0

ckdgus2482 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말