글 읽기 - 반례 부탁드립니다

(追記) (追記ここまで)

반례 부탁드립니다

17265번 - 나의 인생에는 수학과 함께

dlcksdnd321 6년 전 0

반례 부탁드립니다 ᅲᅲ

위에 나와있는 2가지는 맞았습니다

package AlgoStudy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import javax.print.Doc;
public class B17265 {
	static String[][] map;
	static int[][] dist;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(bf.readLine());
		map = new String[size][size];
		dist = new int[size][size];
		for (int i = 0; i < size; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < size; j++) {
				map[i][j] = st.nextToken();
				dist[i][j] = Integer.MIN_VALUE;
			}
		}
		dist[0][0] = Integer.parseInt(map[0][0]);
		PriorityQueue<Dot> pq = new PriorityQueue<>((a, b) -> -(a.value - b.value));
		pq.add(new Dot(0, 0, Integer.parseInt(map[0][0])));
		while (!pq.isEmpty()) {
			Dot dot = pq.poll();
			if (dot.x + 2 < map.length) {
				if (dist[dot.x + 2][dot.y] < cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 2][dot.y]),
						map[dot.x + 1][dot.y])) {
					dist[dot.x + 2][dot.y] = +cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 2][dot.y]),
							map[dot.x + 1][dot.y]);
					pq.add(new Dot(dot.x + 2, dot.y, Integer.parseInt(map[dot.x + 2][dot.y])));
				}
			}
			if (dot.y + 2 < map.length) {
				if (dist[dot.x][dot.y + 2] < cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x][dot.y + 2]),
						map[dot.x][dot.y + 1])) {
					dist[dot.x][dot.y + 2] = cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x][dot.y + 2]),
							map[dot.x][dot.y + 1]);
					pq.add(new Dot(dot.x, dot.y + 2, Integer.parseInt(map[dot.x][dot.y + 2])));
				}
			}
			if (dot.x + 1 < map.length && dot.y + 1 < map.length) {
				if (dist[dot.x + 1][dot.y + 1] < cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
						map[dot.x + 1][dot.y])) {
					dist[dot.x + 1][dot.y + 1] = cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
							map[dot.x + 1][dot.y]);
					pq.add(new Dot(dot.x + 1, dot.y + 1, Integer.parseInt(map[dot.x + 1][dot.y + 1])));
				}
				if (dist[dot.x + 1][dot.y + 1] < cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
						map[dot.x][dot.y + 1])) {
					dist[dot.x + 1][dot.y + 1] = cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
							map[dot.x][dot.y + 1]);
					pq.add(new Dot(dot.x + 1, dot.y + 1, Integer.parseInt(map[dot.x + 1][dot.y + 1])));
				}
			}
		}
		System.out.print(dist[dist.length - 1][dist.length - 1]+" ");
		
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				dist[i][j] = Integer.MAX_VALUE;
			}
		}
		dist[0][0] = Integer.parseInt(map[0][0]);
		pq = new PriorityQueue<>((a, b) -> a.value - b.value);
		pq.add(new Dot(0, 0, Integer.parseInt(map[0][0])));
		while (!pq.isEmpty()) {
			Dot dot = pq.poll();
			if (dot.x + 2 < map.length) {
				if (dist[dot.x + 2][dot.y] > cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 2][dot.y]),
						map[dot.x + 1][dot.y])) {
					dist[dot.x + 2][dot.y] = +cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 2][dot.y]),
							map[dot.x + 1][dot.y]);
					pq.add(new Dot(dot.x + 2, dot.y, Integer.parseInt(map[dot.x + 2][dot.y])));
				}
			}
			if (dot.y + 2 < map.length) {
				if (dist[dot.x][dot.y + 2] > cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x][dot.y + 2]),
						map[dot.x][dot.y + 1])) {
					dist[dot.x][dot.y + 2] = cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x][dot.y + 2]),
							map[dot.x][dot.y + 1]);
					pq.add(new Dot(dot.x, dot.y + 2, Integer.parseInt(map[dot.x][dot.y + 2])));
				}
			}
			if (dot.x + 1 < map.length && dot.y + 1 < map.length) {
				if (dist[dot.x + 1][dot.y + 1] > cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
						map[dot.x + 1][dot.y])) {
					dist[dot.x + 1][dot.y + 1] = cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
							map[dot.x + 1][dot.y]);
					pq.add(new Dot(dot.x + 1, dot.y + 1, Integer.parseInt(map[dot.x + 1][dot.y + 1])));
				}
				if (dist[dot.x + 1][dot.y + 1] > cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
						map[dot.x][dot.y + 1])) {
					dist[dot.x + 1][dot.y + 1] = cal(dist[dot.x][dot.y], Integer.parseInt(map[dot.x + 1][dot.y + 1]),
							map[dot.x][dot.y + 1]);
					pq.add(new Dot(dot.x + 1, dot.y + 1, Integer.parseInt(map[dot.x + 1][dot.y + 1])));
				}
			}
		}
		System.out.print(dist[dist.length - 1][dist.length - 1]);
	}
	static int cal(int a, int b, String oper) {
		if (oper.equals("+")) {
			return a + b;
		} else if (oper.equals("-")) {
			return a - b;
		} else if (oper.equals("*")) {
			return a * b;
		}
		return 0;
	}
	static class Dot {
		int x;
		int y;
		int value;
		public Dot(int y, int x, int value) {
			this.x = x;
			this.y = y;
			this.value = value;
		}
	}
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

반례 부탁드립니다

dlcksdnd321 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말