문제 - 안전영역 질문드립니다. - 인프런

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

문제 - 안전영역 질문드립니다.

작성

144

위 링크에 제가 작성한 코드가 있습니다.

선생님께서 작성하신 코드와 거의 유사하며

차이점으로는 코드라인41번에서 빗물의 높이 d를 1~100 이 아닌 최소/최대 높이값을 구해

for문의 i 범위를 다르게 했습니다.

위와 같이한 이유에는 문제예시를 통해 다음과 같이 정리할 수 있습니다.

가장큰 높이: 9

가장 작은 높이: 2

case1) 빗물의 높이 < 2

=> 잠기는 곳이 하나도 없어서 안전지대 갯수가 1

case2) 2 <= 빗물의 높이 < 9

=> 잠기는 곳이 몇 군데 있어서 안전지대 갯수가 많음

case3) 빗물의 높이 >= 9

=> 모든 곳이 잠겨서 안전지대 갯수가 0

따라서 d변수의 범위를 hmin~ hmax 까지로 해도 되지 않을까 생각했지만 FAIL을 맛볼 수 밖에 없었습니다.

Q1. 왜 1~100으로 해야 올바른 정답이 나오는지 궁금합니다.

Q2. 추가로, 최종정답 값을 보관하는 int maxArea 변수를 0으로 초기화하면 FAIL이 뜨는 것을 확인했습니다. maxArea 변수에 1이 아닌 다른 숫자가 들어가면 안되는 이유도 궁금합니다.

답변 1

지식공유자

안녕하세요. ㅎㅎ

Q1. 왜 1~100으로 해야 올바른 정답이 나오는지 궁금합니다.

>> 이 문제는 "내리는 비의 양에 따른 모든 경우"를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중 최대를 구하는 겁니다. 따라서 문제의 범위인 1 ~ 100으로 하셔야 됩니다.

>> 안전영역 최소값은 1이 됩니다. 비가 안내렸을 경우 1이되기 때문입니다.

감사합니다.

질문자

Q2. 안전영역의 최솟값이 1이 되는 경우를 이해했습니다. 감사합니다.

Q1. "내리는 비의 양" 을 1~100 모두를 검사할 필요가 없다는 생각을 지우지 못했습니다....

빗물 높이)    0 1 2 3 4 5 6 7 8 9 10 11 .... 100
안전지대갯수) 1 1 - - - - - - -  0  0  0 ....   0

지형높이의 최소,최대가 2, 9 일 때 위와같이

으로 영역이 나눠지며 1번쨰와 3번째 영역에서는 안전지대 갯수가 항상 고정적이기 때문입니다.

지식공유자

네 맞는 말씀이세요. 다만 문제에서 1 ~ 100이고 범위가 작기 때문에 굳이 min, max를 기반으로 할 이유가 없어서 1 ~ 100으로 하는 것도 되구요. min, max기반으로 하게 되면 다음 코드 처럼 구축하면 됩니다.