글 읽기 - Bit mask 사용해서 풀었는데 어디가 틀렸을까요ㅠㅠ (java)

asiso 1년 전 0

안녕하세요, Bit mask 사용해서 배열의 각 자리를 더하는 방식으로 합을 구하였습니다.

[틀렸습니다]가 나와서 고민하다 풀이를 봤는데, 로직은 같다고 생각합니다.

(굳이 Bit mask를 사용해서 복잡하게 다 더했을 뿐..)

어디가 잘못 되었을까요?

혹시 반례가 있을까요?ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static int max;
	static int total;
	static int[] weight;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		weight = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			weight[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(weight);
		
		for(int time = 1; time < Math.pow(2, n); time++) {
			total = 0;
			for(int digit = 0; digit < n; digit++) {
				int x = time & (1 << digit);
				if(x != 0) total += weight[digit];
			}
			
			if(total > max + 1) {        // max + 1을 만들지 않고 더 큰 수를 만들었기에
				System.out.println((max + 1));    // max + 1이 측정할 수 없는 최솟값
				System.exit(0);
			}
			if(total > max) max = total;    // max + 1을 만든 경우, max 업데이트
		}
		
		System.out.println((total + 1));    // 모든 추를 사용하여 구한 total + 1
	
	}

}

bamgoesn 1년 전 0

이 문제 n이 최대 1000입니다. Math.pow(2, n)은 정상적으로 계산할 수 없습니다.

asiso 1년 전 0

헉

감사합니다 !!!!!!!!!!!!

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

문제

문제

출처

ICPC

Bit mask 사용해서 풀었는데 어디가 틀렸을까요ㅠㅠ (java)

asiso 1년 전 0

bamgoesn 1년 전 0

asiso 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말