글 읽기 - 재귀로는 안풀리나요?

filot 6년 전 0

지금 재귀로 풀어볼려고 하는데 ... 오른쪽 -> 왼쪽으로 오는 케이스 때문에 잘 안되네요.

그 부분 때문에 stackoverflow가 나는 상황인데... 재귀로는 안되는건지 ..

import java.io.FileInputStream;
import java.util.Scanner;

public class Main {
	static int N;
	static int M;
	static int[][] MAP;
	static int[][] MEMO;
	
	public static void main(String[] args) throws Exception {		
		Scanner scanner = new Scanner(System.in);

		N = scanner.nextInt();
		M = scanner.nextInt();
		
		MAP = new int[N + 1][M + 1];
		MEMO = new int[N + 1][M + 1];
		
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++)
				MAP[i][j] = scanner.nextInt();
		
		int max = move(N, M);
		
		System.out.println(max);

		scanner.close();
	}
	
	public static int move(int n, int m) {
		if (n == 1 && m == 1)
			return MAP[n][m];
		
		if (MEMO[n][m] > 0 )
			return MEMO[n][m];
		
		int left = 0;
		if (canMove(n, m - 1))
			left = move(n, m - 1) + MAP[n][m];
		
		int right = 0;
		if (canMove(n, m + 1))
			right = move(n, m + 1) + MAP[n][m];
		
		int up = 0;
		if (canMove(n - 1, m))
			up = move(n - 1, m) + MAP[n][m];
		
		return MEMO[n][m] = max(left, right, up);
	}
	
	public static boolean canMove(int n, int m) {
		if (n <= 0 || m <= 0 || n > N || m > M)
			return false;
		
		return true;
	}
	
	public static int max(int x, int y, int z) {
		int temp = Math.max(x, y);
		
		return Math.max(temp, z);
	}
}

wowoto9772 6년 전 0

저는 재귀에 메모이제이션을 추가해서 해결했어요.

일단 한가지 걱정되는 부분은,

왼쪽으로 갔다가 오른쪽으로 갔다가

다시 왼쪽으로 갔다가 오른쪽으로 갔다가 뭐 이런식으로 들어 가면, 스택 오버 플로우가 날거 같아요.

아예 방향을 지정해서 들어가는건 어떨까요.

filot 6년 전 0

아예 방향을 지정해서 들어간다는게 무슨 의미일까요? 지금 생각해보니 오른쪽으로 갔다가 왼쪽으로 서로 반복을 하니 스택오버 플로우가 나긴할텐데 ..

이걸 어떻게 해결을 해야할지 감이 안오네요.

혹시 조금더 힌트를 주실 수 없나요?

wowoto9772 6년 전 0

처음 부터 다음 방향을 정해두는거에요.

예를들면

filot님 코드에서는 맨 밑에서부터 위로 가는 거 잖아요.

(i,j)위치에 있다고 가정할때, 위로 올라갔을때,

거기서 방향은 왼쪽으로만 가게하거나 오른쪽으로만 가게하는 거죠.

filot 6년 전 0

힌트 감사합니다.

wowoto9772님의 코드를 참고해서 수정을 했는데

자바로 메모이제이션을 하면 시간초과가 나올 수 밖에 없는건지 모르겠네요 ㅠㅠ

언어적 특성인지....

import java.io.FileInputStream;
import java.util.Scanner;

public class Main {
	static int N;
	static int M;
	static int[][] MAP;
	static long[][][] MEMO;
	
	public static void main(String[] args) throws Exception {		
		Scanner scanner = new Scanner(System.in);

		N = scanner.nextInt();
		M = scanner.nextInt();
		
		MAP = new int[N + 1][M + 1];
		MEMO = new long[N + 1][M + 1][2];
		
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++)
				MAP[i][j] = scanner.nextInt();		
		
		System.out.println(Math.max(move(N, M, 0), move(N, M, 1)));

		scanner.close();
	}
	
	public static long move(int n, int m, int p) {
		if (n <= 0 || m <= 0)
			return Integer.MIN_VALUE;
		
		if (n == 1 && m == 1)
			return MAP[n][m];
		
		if (MEMO[n][m][p] > 0 )
			return MEMO[n][m][p];
		
		long left = Integer.MIN_VALUE;
		if (canMove(n, m - 1) && p == 0)
			left = move(n, m - 1, p) + MAP[n][m];		
		
		long right = Integer.MIN_VALUE;
		if (canMove(n, m + 1) && p == 1)
			right = move(n, m + 1, p) + MAP[n][m];
		
		long up = Integer.MIN_VALUE;
		if (canMove(n - 1, m))
			up = Math.max(move(n - 1, m, 0), move(n - 1, m, 1)) + MAP[n][m];
		
		return MEMO[n][m][p] = max(left, right, up);
	}
	
	public static boolean canMove(int n, int m) {
		if (n <= 0 || m <= 0 || n > N || m > M)
			return false;
		
		return true;
	}
	
	public static long max(long x, long y, long z) {
		long temp = Math.max(x, y);
		
		return Math.max(temp, z);
	}
}

indioindio 6년 전 0

1000 * 1000이면 scanner로 인한 손해도 꽤 될 것 같아요

bufferedstreamreader(??) 였나를 사용해보세요요

indioindio 6년 전 0

실험해보니 BufferedReader를 사용하면 100만개의 수를 입력받는데 0.8초 정도,

scanner로는 2.5초 정도 걸리네요

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

문제

문제

출처

ICPC

재귀로는 안풀리나요?

filot 6년 전 0

wowoto9772 6년 전 0

filot 6년 전 0

wowoto9772 6년 전 0

filot 6년 전 0

indioindio 6년 전 0

indioindio 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말