https://www.acmicpc.net/problem/24343
대충 번역기 돌려보면 두 기계가 있고 n개의 부품을 T시간 이내에 만들수 있으면 1,아니면 0출력하는 문제인데요..
아무리 봐도 그냥 집합 2분할 해서 각각의 부분집합의 합이 모두 T이하인 경우가 있는지 물어보는 문제인데 풀리지가 않네요 ㅜ
살려주세요
대충 번역기 돌려보면 두 기계가 있고 n개의 부품을 T시간 이내에 만들수 있으면 1,아니면 0출력하는 문제인데요..
아무리 봐도 그냥 집합 2분할 해서 각각의 부분집합의 합이 모두 T이하인 경우가 있는지 물어보는 문제인데 풀리지가 않네요 ㅜ
살려주세요
랜디하다가 나온건가..?
s2~g4 랜디에서 어쩌다 평균 시도율로 정렬해서 제일 위에 눌렀다가 잘못 걸렸어요..
냅색 안됨? 내용을 정확히 못읽겠어서 정확한 제한을 모르겠네
N * 숫자의 최대치(합 아님) 으로 생각해보셈
냅색으로 한 30번째 맞왜틀 중이라서요..
주어진 부품을 어떻게 절반으로 나눌 수 있는지 모든 경우의수를 구하는건 O(NT) dp로 가능함. 나올 수 있는 부품 합이 최대 10만이니까 T는 5만까지만 계산하고, 테케가 최대 10개니까 충분히 시간 안에 돌 듯
냅색으로 풀었는데 계속 맞왜틀이에요ㅜ
개수가 10개 이하라2^n아님? 합이 아니라 최대치 냅색은 50 50 51 이렇게 다 더했다가 다 빼는걸 고려못합
10은 아마 테스트 케이스 갯수고 0<n<1001인것 같네요