백준 2437 저울

 

 

 

문제를 처음봤을 때 너무 꼬아서 접근을 했던 것 같다.

max가될 수 있는 추 무게부터 min의 추 무게까지 그 사이값들 하나하나 맞춰지나 판별하고 있었다.. 

정답은 나왔지만 결과는 당연히 시간초과. 

방황했던 흔적은 아래와 같다.

 

 

 

 

 

 

다른 방법이 있겠지하고 검색한 결과 너무 간단해서 놀랐다.

누적합이라는 개념을 이해하고 있으면 쉽게 풀 수 있었던 문제인데, 누적합에 대해선 다음 사이트를 참고해서 이해했다.

 

https://novlog.tistory.com/9

[C/C++] BOJ(백준) 2437 "저울" 문제 풀이

 

 

 

정리하자면, 이 문제에서 핵심은 "만들 수 있는 무게의 합이 절대 끊이지 않아야 한다"는 것이다.

기존에 측정가능했던 구간이 [1, 5]일때 5이라는 무게가 등장했다고하면,

추가로 측정 가능한 구간 [6, 10]이 생기고 기존구간과 이어졌을 때 [1,10]이 되면서 결국 끊기지 않는구간이 완성된다. 

하지만 기존구간 [1. 5]에서 10이라는 무게가 등장했다고 하면,

[11,15]구간이 새로 생기지만 5~11사이의 공백이 생겨버린다.

 

누적합 알고리즘

 

다음과 같이 새로운 무게 v[i]가 등장했을 때 기존구간 sum+1을 벗어나면 안된다.

벗어나는 순간 반복문이 종료되고 계속 더했던 기존구간sum이 정답이 된다.

출력값은 처음으로 연속값이 안나오는 경우이므로 +1해서 출력한다!