글 읽기 - 14888 틀린 이유를 모르겠습니다

vision929 4년 전 0

예시 데이터엔 정상적으로 나오고 다른 데이터도 테스트 해보았을 때 잘 나오는 것 같은데 어째서인지 틀렸네요

여러번 디버깅을 하였지만 감이 잡히질 않아 질문 드립니다

boolean 타입 배열을 이용하여 연산자 경우의 수를 전부 사용해보도록 백트랙킹 풀이인데 뭐가 잘못되었을까요

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static long min;
	static long max;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());
		int[] num = new int[n];
		int[] op = new int[4];
		
		StringTokenizer st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < num.length; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(bf.readLine());
		ArrayList<Character> chOp = new ArrayList<Character>();
		for (int i = 0; i < op.length; i++) {
			op[i] = Integer.parseInt(st.nextToken());
			for (int j = 0; j < op[i]; j++) {
				if (i == 0)
					chOp.add('+');
				else if (i == 1)
					chOp.add('-');
				else if (i == 2)
					chOp.add('x');
				else
					chOp.add('/');
			}
		}
		
		boolean[] visited = new boolean[chOp.size()];
			
		max = -100000000;
		min = 100000000;
		
		func(n, 0, visited, num, chOp, num[0]);
		
		System.out.print(max +"\n" + min);
	}
	
	static public void func(int n, int pos, boolean[] visited, int[] num, ArrayList<Character> chOp, long k) {
		long result = 0;
		
		if (pos == n - 1) {
			if (k < min)
				min = k;
			
			if (k > max)
				max = k;	
			return;
		}
		for (int i = 0; i < chOp.size(); i++) {
			if (!visited[i]) {
				visited[i] = true;
				if (chOp.get(i) == '+') {
					result = k + num[pos + 1];
				} else if (chOp.get(i) == '-') {
					result = k - num[pos + 1];
				} else if (chOp.get(i) == 'x') {
					result = k * num[pos + 1];
				} else {
					result = k / (long) num[pos + 1];
				}
				func(n, pos + 1, visited, num, chOp, result);
				visited[i] = false;
			}
		}
	}

}

vision929 4년 전 1

ㅋㅋ min 과 max 를 10억 -10억이 아니라 -1억 1억으로 했네요...

디버깅을 작은 숫자로 백날 해봤자 소용없네요;ㅋㅋ..

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

문제

문제

출처

ICPC

14888 틀린 이유를 모르겠습니다

vision929 4년 전 0

vision929 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말