백준 2437번 저울 (1) 썸네일형 리스트형 [백준/C++/KOI] 2437번 저울 증명 및 풀이 문제를 처음 읽었을 때 dp라는 생각이 스쳐지나갔는데 100만개의 저울추가 1000까지의 숫자를 가지면 배열로 만들 수 없을만큼 큰 수가 되니 포기하고 1초라면 1억번 연산이니 최대 N log N 일 것이라고 생각하였다. sorting 한 번으로 구할 수 있다는 소리인데... 도저히 그리디로 풀 방법이 떠오르지 않아 질문 게시판의 도움을 얻으니 배열에서 다음에 오는 숫자가 기존 숫자들의 합보다 작으면 다음에 오는 숫자까지 더한 값까지 모든 수를 나타낼 수 있다 라는 힌트를 얻었고 이를 증명하고자 한다. Prove S(k) = ∑a[k] 이고 S(K)는 1 ~ S(K)까지 모든 수를 표현할 수 있을 때, S(k) + a[k+1]는 S[k] + a[k+1]까지 모든 수를 표현할 수 있다. Basis S(1).. 이전 1 다음
