zestbear   3년 전

코드 설명을 드리자면, 우선순위는 가장 큰 수로 나누는 3으로 나누기 -> 2로 나누기 -> 1 뺴기로 하였습니다.

그런데 41을 예시로 하던 도중 제가 직접 한 것과 프로그램을 돌려 얻은 최솟값이 다른 것을 발견했습니다. 프로그램 중간중간에 printf를 넣어 알아보니 10이 프로그램에서는 저와 다르게 2로 바로 나누지 않고 1을 먼저 뺀 것을 알 수 있었습니다. 또 다른 변수가 있는지 많은 숫자들을 예시로 직접 해보았지만. 10과 100밖에 없었습니다. 여기서 가설을 세우게 된 것이, 10의 제곱수에서 변수가 발생한다였습니다. 10의 제곱수에서 1을 빼면 3으로 나눌 수 있으니까요.

따라서 '10의 제곱수일 경우 1을 먼저  뺴라' 라는 식을 추가하였습니다. 그에 따라 우선순위도 3으로 나누기 -> 10의 제곱수일 경우 1을 먼저 빼기 -> 2로 나누기 -> 나머지 경우의 수에선 1을 빼기 로 수정한 다음 프로그램을 돌려본 결과, 넣는 모든 예시들이 저의 예상과 동일하게 나온 것을 확인할 수 있었습니다. 하지만 제출을 하니 틀렸습니다 만 나올 뿐이라 어디가 잘못되었는지, 또 어떤 다른 변수가 있는지 궁금하여 게시판에 글을 쓰게 되었습니다. 

감사합니다.

dldyddlwl   3년 전

반례 

16

예상] 16 -> 8 -> 4 -> 2 -> 1

글쓴이님의 코드]  16->15-> 5 -> 4 ->3 ->1

khyunchoi   3년 전

코드적인 실수는 윗분이 잘 지적해주신것 같고

우선순위를 두는 식으로 코딩을 하면 많은 반례가 발생할 수 밖에 없습니다.

저는 방금 정답처리 받고 오는 길인데

제가 연구한 과정에서 알아낸 반례를 말씀드리자면

28 같은 경우


최소루트)   28 > 27 > 9 > 3 > 1

글쓴이루트)28 > 14 > 7 > 6 > 2 > 1


10제곱이 아니어도 이런 케이스가 꽤 있을 것 같습니다.

zestbear   3년 전

관심 가져 주시고 알려 주셔서 감사힙니다.

댓글을 작성하려면 로그인해야 합니다.