• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

6 -B 모범답안의 line 6은 반례라고 보면 될까요?

23.11.29 07:27 작성 조회수 103

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

답변 1

답변을 작성해보세요.

2

큰돌님의 프로필

큰돌

지식공유자

23.11.29 08:18

안녕하세요 ㅎㅎ

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라는 조건이 나오게 됩니다.

 

이런 부분을 생각 못했을 때는 반례를 생각하는 부분으로 접근하는게 맞을까요?

>> 넵 무조건 반례를 생각해주세요. 이렇게 생각하시면 됩니다. 실버까지는 반례를 거의 안생각해도 됩니다. 그러나 골드이상부터는 무조건 자신의 로직 + 반례를 생각한 로직 = 정답로직이라고 생각하시면 됩니다.

 

 

감사합니다.

 

mhyim님의 프로필

mhyim

질문자

23.11.29 21:46

모호한 질문이었는데 원하는 답변에 이어서 팁까지 얻었습니다 ㅜㅜ 정말 감사합니다.