-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
6 -B 모범답안의 line 6은 반례라고 보면 될까요?
23.11.29 07:27 작성 조회수 156
0
큰돌님 안녕하십니까?
해당문제 큰돌님과 비슷하게 접근까지하여 예제 까지는 통과 하였습니다.
아래 코드는 큰돌님 모범 답안 중 일부인데요,
볼드 처리 한 부분을 생각못해서 50%에서 틀린 것 같습니다.
지금이야 해설과 강의를 보고 그럴 수 있겠구나 하지만, 이런 부분을 생각 못했을 때는 반례를 생각하는 부분으로 접근하는게 맞을까요?
bool check(int mid){
if(mx > mid) return false; // line 6
...이하 생략
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> a[i];
sum += a[i];
mx = max(mx, a[i]);
}
...이하 생략
아래는 큰돌님 모범답안 링크입니다.
https://www.acmicpc.net/source/share/e575431157ef40f48ecb65d4426ffbcb
답변을 작성해보세요.
2
큰돌
지식공유자2023.11.29
안녕하세요 ㅎㅎ
bool check(int mid){
if(mx > mid) return false; 이 부분이군요.
이거는 문제의 조건을 잘 녹여내야겠다. 라는 게 체화되어있으면 됩니다.
문제를 보시면
1번 블루레이에 1, 2, 3, 4, 5, 2번 블루레이에 6, 7, 3번 블루레이에 8, 9 를 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에, 블루레이의 크기는 17이 된다. 17보다 더 작은 크기를 가지는 블루레이를 만들 수 없다.
이렇게 힌트주는 부분으로 봤을 때 블루레이에 k개를 담아야하며
길이가 가장 큰 기타강의 또한 무조건 블루레이에 들어가야 하기 때문에 (최대 블루레이의 길이 : mx) > mid라는 조건이 나오게 됩니다.
이런 부분을 생각 못했을 때는 반례를 생각하는 부분으로 접근하는게 맞을까요?
>> 넵 무조건 반례를 생각해주세요. 이렇게 생각하시면 됩니다. 실버까지는 반례를 거의 안생각해도 됩니다. 그러나 골드이상부터는 무조건 자신의 로직 + 반례를 생각한 로직 = 정답로직이라고 생각하시면 됩니다.
감사합니다.
답변 1