글 읽기 - 1806번 왜 틀렸는지..ㅠ

daeshinhigh 9년 전 0

샘플입력 등 몇개 넣어서 해봐도 답은 나오는것 같은데

채점하면 틀렸다고나오네요.ㅠㅠ

고수님들 조언좀..부탁드립니다

import java.util.*;
 
public class Main {
 
    public static int cnt(int aa){
		int ans=0;
		int remind=0;
		while(aa > 0){
			remind = aa%2;
			aa = aa/2;
			if(remind ==1){
        		ans++;
        	}
		}
		return  ans;
	}
	
	public static void main(String args[]) throws Exception
	{       
		Scanner sc = new Scanner(System.in);
        int T,a;

        T = sc.nextInt();
        a = sc.nextInt();
        Integer[] b = new Integer[T];
       
        for (int i = 0; i < T; i++) {
			b[i] = sc.nextInt();
		}

//        Integer[] a = {1,2,3,4};
      
        int sum = 0;
        int answ = 0;
        int min = 100000;
        
        for (int i = 0; i < ( 1 << (T)); i++) {
        	for (int j = 0; j < T; j++) {
  

				if(0 != (i & (1 << j))){					
					sum+= b[j];
					if(sum == a){
						answ = cnt(i);
						
						if(answ < min){
							min = answ;
						}
						
					}
				}
			}
        	sum = 0;
		}
        if(min == 100000) min = 0;
        System.out.println(min);
        
	}
}

Nada 9년 전 0

연속하는 수열의 합의 최대값을 구하는 문제입니다.

또 2^T를 하셨는데 시간복잡도가 O( 2^100000 ) 이 되어 시간초과를 받으실 것 같아요.

daeshinhigh 9년 전 0

음 시간초과는 안나오고 틀렸습니다 에요 ㅠ 어떤케이스가 틀리는지 모르겠네요

Nada 9년 전 0

3 2

1 3 1

일 경우 답은 1입니다.

위 소스로는 2가 나올 것 같네요.

Nada 9년 전 0

또 시간초과가 발생 하지 않은 이유는

큰 데이터를 입력으로 넣기 전에 작은 데이터에서 틀려서 틀렸습니다를 받은 것 같네요.

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

문제

문제

출처

ICPC

1806번 왜 틀렸는지..ㅠ

daeshinhigh 9년 전 0

Nada 9년 전 0

daeshinhigh 9년 전 0

Nada 9년 전 0

Nada 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말