[Week of Line Sweep] BOJ 1911 #2

생각보다 풀이 방법은 간단했다.

참조 - (haedallog.tistory.com/142)

 

각 점들을 오름차순으로 정렬한 뒤, 1개씩 순회하면서

1. 시작점 s와 현재 점의 시작 값의 최댓값을 s로 놓는다.

2. (끝점 - s + 널빤지 길이 l - 1) 나누기 l 후 몫에 대한 값만 count에 넣는다.

3. 결괏값에 count를 증분 해주고

4. s에 count * l을 해주어 시작점을 이동한다.

 

예제의 값 기준으로 보면(n=3, l=3)

물웅덩이 1 [1, 6]

물웅덩이 2 [8, 12]

물웅덩이 3 [13, 17]

 

[첫 번째 순회]

s = 1이 되고(0, 1중 1이 크므로. s의 초기값은 0)

count = (6 - 1 + 3 - 1) // 3 = 2

res = 2

s = 1 + 2 * 3 = 7

 

[두 번째 순회]

s = 8이 되고(7, 8중 8이 크므로)

count = (12 - 8 + 3 - 1) // 3 = 2

res = 4

s = 8 + 2 * 3 = 14

 

[세 번째 순회]

s = 14(13, 14중 14가 크므로)

count = (17 - 14 + 3 - 1) // 3 = 1

res = 5

s = 14 + 1 * 3 = 17

 

다른 것보다 count를 구할 때

l을 더한 뒤 1을 빼주는 게 좀 이해가 안 가서

물웅덩이 1이 [1,7]이라고 가정하고 계산을 해봤다.

s = 1

count = (7 - 1 + 3 - 1) // 3 = 8 // 3 = 2

물웅덩이 1은 널빤지 2개가 막을 수 있는 최댓값이므로 count의 값은 맞다.

 

여기서 물웅덩이 1이 [1,8]이라고 가정하고 계산을 해보면

s = 1

count = (8 - 1 + 3 - 1) // 3 = 9 // 3 = 3

물웅덩이 1은 널빤지 3개는 돼야 막을 수 있으므로 count의 값이 맞다.

(물웅덩이의 넓이가 7이므로)

 

상기의 계산법을 잘 기억해놨다가

나중에 비슷한 Case에 적용할 수 있으면 좋겠다.

 

누군가의 해설을 보고 푼 문제라 조금 찝찝함이 남았지만

그래도 이렇게 하나씩 배워 가는 거겠지.. 처음부터 잘하는 사람은 없으니까!