당니의 개발자 스토리
1-H 본문
내 풀이(http://boj.kr/9bb115b9d6544242a4fa51841fd3fa22) - 맞음
공유 소스 보기
www.acmicpc.net
1-H
자 1-H 백준 2559 수열 문제를 풀어 보도록 할게요.
자 N은 1에서 10만이고 K는 1에서 10만이니까 10만 - 1이죠. 왜냐면 N 사이값이라고 했으니까요.
사이값 이라는 거는 그 범위를 뺀다라고 하는 거거든요.
그래서 이 문제는 연속된 온도의 합이 연속된 온도의 합이 최대가 되는 값을 구하라라는 건데, 여러분 어떤 생각이 나요?
바로 구간합이 생각이 나야 돼요.
문제에서 중요했던 점은 뭐냐면, 사실은 이 문제의 최소값을 정하는게 중요해요.
문제에서 최대값을 구하라라고 하면은 최소값에서부터 최대값을 구하는 거에요.
만약 문제에서 최소값을 구하라 라고 하면은 최대값에서부터 최소값을 구하라 라는게 되는 거에요.
저희가 최대값을 구할 때 어떤 로직을 쓰죠?
ret = max(ret, value); 이런 식으로 하죠. 그러니까 즉, ret에다가 최대값을 계속해서 갱신해나가면서 ret을 만들고 그걸 기반으로 최종적인 최대값을 만들어서 문제에다가 반환을 하는거죠.
자 그러면은 최소값은 어떻게 할까요?
마찬가지로 ret에다가 계속해서 최소값을 쌓아가면서, 계속 갱신해나가면서 최소값을 만드는 거죠.
이제 최소값부터 해야 되는 건 알겠어요. 그럼 최소값을 뭘로 설정해야 될까요?
그건 바로 이 문제의 최소값을 결정하는 거예요.
자 이 문제를 최악으로 한번 가정을 해보죠.
이 문제가 -100자리가 10만 번 나온다고 해볼게요. 근데 그럼 k는 최대 10만 - 1 이니까 -100 X (10만 - 1) 이런 식으로 하게 되겠죠.
근데 이렇게 쓰면 귀찮으니까
이렇게 해보면은 어림잡아 -1000만이라고 볼 수가 있겠죠.
이렇게 해서 '아 이 문제의 최소값은 -1000만이구나' 하고 들어가는 거예요.
근데 지금 보시면 -100004라고 했죠? 이거는 뭐냐면 이 문제는 사실은 -1000만으로 해도 돼요.
근데 사실 문제를 풀다 보면 사이가 아닐 때도 있고, -1000만이 문제 답의 범위에 걸치고 -1000만 - 1를 해가지고 -1001만부터 해야 되는 그런 문제들이 있을 거예요.
그래서 끝점(-1000만)보다는 더 약간 버퍼 같은 역할을 하는 어떤 수를 넉넉하게 마이너스를 해주거나, 플러스 해주는게 좋다고 교안에 쓴 적이 있을 겁니다.
그래서 이거는 약간 팁같은거에요. 이렇게 해야 문제를 디버깅할 때 맞왜틀, '어 이거 맞는데 왜 틀리지' 이런 거에 안 걸릴 수 있다 라는 겁니다.
코드는 위와 같습니다. 최대값에다가 최소값을 넣어 비교하는 것과 범위에 유의하시면 됩니다.
