[BOJ] 2473. 저울

https://www.acmicpc.net/problem/2437 접근 방법 아이디어만 있다면 풀 수 있는 문제이다. 물론... 그 기발한 아이디어가 없어서 질문 검색을 통해 그 아이디어를 얻게 되었다. 아이디어는 이러하다. 먼저 n번째 까지의 누적값을 Sn 이라 해보자. 그리고 배열에서 n번째 값을 An 이라 하자. 그리고 S(n-1) 보다 만약 (An)-1값이 크면 S(n-1) ~ A(n-1) 의 값은 만들지 못한다. 따라서 만들 수 없는 최솟값은 S(n-1) 이 된다. 내가 생각하는 증명은 이러하다. Sn은 1부터 시작할 것이다. 왜냐하면 첫번째 원소가 2라면 제일 최솟값인 1을 만들지 못하기 때문이다. 그럼 이제 차근차근 값들이 더 해가지면서 만들 수 있는 조합들이 무수하게 많아질 것이다. 하지만..

2020.08.12