글 읽기 - 브루트포스 (81% 오답) // 반례가 있을까요.. 어디에서 틀렸는지 모르겠습니다

pia2011 3년 전 0

1페이지에 어떤분이 올려주신 반례를 다 넣어 봤을 때도 잘 되는데 왜 안되는지 모르겠습니다..

import java.io.*;
import java.util.*;

// 항상 나보다 더 나은 방법이 있다

public class Main {
		
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	static int solve2(int[][] board,int n, int m, int i, int j){

		ArrayList<Integer> alist = new ArrayList<Integer>();

		if (i + 1 < n && j + 1 < m && j - 1 >= 0)
			alist.add(board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j - 1]); // ㅜ
		
		if (i - 1 > 0 && j - 1 >= 0 && j + 1 < m)
			alist.add(board[i][j] + board[i - 1][j] + board[i - 1][j + 1] + board[i - 1][j - 1]); // ㅗ
		
		if (i + 1 < n && i - 1 >= 0 && j + 1 < m)
			alist.add(board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i - 1][j + 1]); // ㅓ
		
		if (i + 1 < n && i - 1 >= 0 && j - 1 >= 0)
			alist.add(board[i][j] + board[i][j - 1] + board[i + 1][j - 1] + board[i - 1][j - 1]); // ㅏ

		if(alist.isEmpty()) return 0;
		
		int max = alist.get(0);
		for (int x : alist) {
			if (x > max)
				max = x;
		}
		return max;
	}
	
	static int solve(int [][] board,boolean [][] check,int n, int m,int i, int j, int sum, int cnt) {
		
		if(cnt >= 3) // 0 에서 3번(1,2,3) 
			return sum;
		
		ArrayList<Integer> alist = new ArrayList<Integer>();
		
		if(i + 1 < n && !check[i+1][j]) {
			check[i+1][j] = true;
			alist.add(solve(board,check,n,m,i+1,j,sum + board[i+1][j], cnt + 1));
			check[i+1][j] = false;
		}
		if(i - 1 >= 0 && !check[i-1][j]) {
			check[i-1][j] = true;
			alist.add(solve(board,check,n,m,i-1,j,sum + board[i-1][j], cnt + 1));
			check[i-1][j] = false;
		}
		if(j + 1 < m && !check[i][j+1]) {
			check[i][j+1] = true;
			alist.add(solve(board,check,n,m,i,j+1,sum + board[i][j+1], cnt + 1));
			check[i][j+1] = false;			
		}
		if(j - 1 >= 0 && !check[i][j-1]) {
			check[i][j-1] = true;
			alist.add(solve(board,check,n,m,i,j-1,sum + board[i][j-1], cnt + 1));
			check[i][j-1] = false;
		}
		
		int max = alist.get(0);
		for(int x : alist) {
			if(max < x)
				max = x;
		}
				
		return max;
		
	}
	public static void main(String[] args) throws IOException {
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] board = new int[n][m];
		boolean[][] check = new boolean[n][m];
		
		for(int i = 0 ; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j<m; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int max = 0;
		int tempt = 0;
		for(int i = 0 ;i<n; i++) {
			for(int j = 0; j<m; j++) {							
				check[i][j] = true;
				tempt = solve(board,check,n,m,i,j,board[i][j],0);
				check[i][j] = false;
				if(tempt > max)
					max = tempt;
			}
		}
		
		// ㅜ ㅏ ㅗ ㅓ 찾기
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				tempt = solve2(board,n,m,i,j);
				if(tempt > max)
					max = tempt;
			}
		}
		
		
		System.out.println(max);
	}
}

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

문제

문제

출처

ICPC

브루트포스 (81% 오답) // 반례가 있을까요.. 어디에서 틀렸는지 모르겠습니다

pia2011 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말