목록99클럽 코딩테스트준비 (1)
원하는 것은 뭐든지
99클럽 코테 스터디 24일차 - 백준 , 저울
문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 문제풀이문제 해석1. 한쪽에는 무게추 한쪽에는 물건을 두어서 물건의 무게를 맞추려고 한다.2. 무게추들이 주어질 때 무게추들의 조합으로 측정할 수 없는 최소의 값을 찾아라문제 풀이1. dfs는 N이 1000개 까지라 2^1000승으로 시간 초과가 발생한다.2. 누적합을 이용하면 된다.3. 무게추들을 가벼운 무게 순으로 정렬한 뒤 누적합을 시작한다.4. 만약 누적합+1 이 다음 무게추의 무게보다 가볍다면 멈춘다.5. 왜냐하면 누적합 + 1 무게를 만들 수가 없기 때문이다. - 이유를 생각해보자 가장 작은 무게 추가 2일 때 시작한다면 누적합이 0이고 0+1은 2보다 작다. - 이처럼 위의 조건을 만족하지 못하면 무게추의 조합으로 해..
개발/문제풀이
2024. 11. 20. 16:50