강의로 돌아가기
임경현

흠... 무엇을 더 생각해 보아야 할까요?

여벌이 있는 학생들로 반복문을 돌렸습니다.
for문으로 reserve.size()만큼이요.

각 여분이 있는 학생에 대해서

  1. 도둑 맞았으면 continue
  2. 이전 번호와 다음 번호가 도둑맞았는지 검사
  3. 둘다 도둑맞지 않았므면 continue

4-1. 이전 번호만 도둑맞고 전 번호에게 빌리지 않았으면 빌려주기
( int losts = lost.size(); -> losts-- // 빌렸는지 check하는 배열에 빌린것으로 표시 )

4-2. 다음 번호만 도둑 맞았으면
( 똑같이 losts 감소시키고 빌린거로 check)

4-3. 둘다 도둑 맞았으면

  • 이전 번호가 빌리지 못했으면 이전 번호에게
  • 이전 번호가 빌렸으면 다음 번호에게

를 반복하고
마지막에 전체 학생수에서 남은 losts를 빼줍니다.

이렇게 알고리즘을 구성했는데요 2개 맞고 다 틀리다고 해서...........
반례하나만 들어 주시거나 뭐가 부족한지 알 수 있을 까요?

그리드 알고리즘이라고 해서 해당 상황에서 최적의 선택을 하게 만든것 같은데...
이것 만드론 부족한 것 같기도 하고 흠... 어렵네요

  • JandB
    여벌이 있는 학생들로 반복문을 돌렸습니다. << 이부분이 좀 이상합니다. 문제에 여벌이 있는 학생도 도둑맞을 수 있다라고 되어있습니다. JandB 2018.09.20 12:57
  • 임경현
    네. 그래서 1번에 lost에 여벌있는 학생의 번호가 있으면 continue로 아무것도 안하고 넘겼습니다. 임경현 2018.09.20 14:49
1 개의 답변
JandB

반례
n = 5 , lost=[2,4,5], reserve=[1,4] 제대로 했다면 output은 4입니다.

  • 임경현
    4번은 잃어 버려서 빌려 주지 못하고 1번만 2번한테 빌려줘서 4,5번이 참가 못하니까 3 아닌가요??? 임경현 2018.09.20 14:48
  • JandB
    지문을 읽어보시면 >>> 당연히 체육복을 2벌 가져온 학생의 체육복이 도난을 당했다면, 여벌의 체육복을 빌려줄 수 없습니다. JandB 2018.09.20 15:08
  • JandB
    "여벌의 체육복을 빌려줄 수 없습니다." <<< 잘 판단 해보세요. ^_^ JandB 2018.09.20 15:09
  • 임경현
    아....................... 감사합니다 임경현 2018.09.20 15:18
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.