글 읽기 - 자바 87퍼에 틀렸습니다.

so971007 2년 전 0

처음에 dfs, bfs로 풀었다가 시간초과나서

bfs+dp로 풀어보려고 노력했는데 이번엔 틀리네요

5퍼센트에서 87퍼센트까지 왔다....

아...........

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

public class Main {
	static int N;
	static String[][] oper;
	static int[][] num;
	static int jump = 0;
	static int max = Integer.MIN_VALUE;
	static int dp[][];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.valueOf(st.nextToken());
		oper = new String[N][2];
		num = new int[N][2];
		dp = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String select1 = st.nextToken();
			String select2 = st.nextToken();
			oper[i][0] = String.valueOf(select1.charAt(0));
			num[i][0] = Integer.valueOf(select1.charAt(1) - '0');

			oper[i][1] = String.valueOf(select2.charAt(0));
			num[i][1] = Integer.valueOf(select2.charAt(1) - '0');
		}
		bfs();
		if (max <= 0) {
			System.out.println("ddong game");
		} else {
			System.out.println(max);
		}
	}

	public static void bfs() {
		Queue<Node> que = new LinkedList<>();
		que.add(new Node(0, 1, 0));

		while (!que.isEmpty()) {
			Node info = que.poll();
			if (info.idx == N) {
				max = Math.max(max, info.result);
				continue;
			}
			int n1 = parsing(info.result, oper[info.idx][0], num[info.idx][0]);
			int n2 = parsing(info.result, oper[info.idx][1], num[info.idx][1]);
			int compare = -1;
			if (n1 > n2) {
				compare = n1;
			} else {
				compare = n2;
			}
			if (dp[info.idx][info.jump] > 0) {
				if (compare > dp[info.idx][info.jump]) {
					dp[info.idx][info.jump] = compare;
					que.add(new Node(info.idx + 1, compare, info.jump));
				}
			} else {
				dp[info.idx][info.jump] = compare;
				que.add(new Node(info.idx + 1, compare, info.jump));
			}

			if (info.jump == 0 && compare < info.result) {
				que.add(new Node(info.idx + 1, info.result, 1));
			}
		}
	}

	public static int parsing(int n, String oper, int m) {
		if (oper.equals("+")) {
			return n + m;
		} else if (oper.equals("-")) {
			return n - m;
		} else if (oper.equals("*")) {
			return n * m;
		} else {
			return n / m;
		}
	}

	public static class Node {
		int idx, result, jump;

		public Node(int idx, int result, int jump) {
			this.idx = idx;
			this.result = result;
			this.jump = jump;
		}
	}
}

seolminsik 1년 전 0

제가 87퍼에서 틀렸을 때는 '매턴마다' 0이하로 떨어지는 경우가 아니고 전체 계산 이후 0이하인 경우만 봤었기 때문이었는데 한 번 그 점이 맞는지 다시 확인해보시면 될 것 같습니다.

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

문제

문제

출처

ICPC

자바 87퍼에 틀렸습니다.

so971007 2년 전 0

seolminsik 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말