2309번 - 일곱 난쟁이
소스코드에서 소팅을 앞에서 9명의 난쟁이를 먼저 소팅하게 해서
제출하면 맞았다고 나오고
알고리즘부터 진행해서 7명을 뽑아낸 후 7명을 소팅하게 해서
제출하면 틀렸다고 나오네요
결국 답은 둘다 똑같이 나오는것같은데요.. 무슨 반례가 있는걸까요?
아무리 생각해도 두 차이를 모르겠네요
알고리즘은 전체 합에서 두 난쟁이의 합을 뺐을 때 100이 되었을 때
그 두 난쟁이를 제거하는 방식입니다.
https://www.acmicpc.net/board/...
저는 소팅을 먼저하니까 맞았다고나오네요..
그리고 답 찾으면 이중루프 둘다 탈출하게 해놨습니다
정렬을 먼저 하지 않을 경우 다음과 같은 케이스에서, 2 하나만 제거해도 100이 나오기 때문에 잘못된 순간에 20번째 줄에서 탈출하게 됩니다.
정렬을 먼저 할 경우 그 하나를 제거하는 것으로 100이 나올 수 있다면 그 이전에 이미 둘을 제거해서 답을 만들 수 있어야 하므로 정답을 찾아낼 수 있습니다.
와..그런반례가있었네요 원소 하나만 빼도 100이 되서 정답으로 간주하는 경우를 생각못해줬네요 감사합니다!!
함수화를 시켜서 올바른 인덱스일때 인덱스 저장하고 바로 리턴시키니까 뒤에서 소팅해도 되네요!
댓글을 작성하려면 로그인해야 합니다.
tjqansthd 5년 전
소스코드에서 소팅을 앞에서 9명의 난쟁이를 먼저 소팅하게 해서
제출하면 맞았다고 나오고
알고리즘부터 진행해서 7명을 뽑아낸 후 7명을 소팅하게 해서
제출하면 틀렸다고 나오네요
결국 답은 둘다 똑같이 나오는것같은데요.. 무슨 반례가 있는걸까요?
아무리 생각해도 두 차이를 모르겠네요
알고리즘은 전체 합에서 두 난쟁이의 합을 뺐을 때 100이 되었을 때
그 두 난쟁이를 제거하는 방식입니다.