642

10

------- 스포 주의 --------

if / elif 차이로 답 차이나는게 이해가 안되시는 분 에겐 가능한 반례입니다.

저는 개인적으로 어느정도 숫자가 커지면 무조건

3으로 나누는게 2로 나누는 것 보다 무조건 좋다고 생각해서 처음에는 elif를 사용했었습니다.

그러다 오답을 확인하고, elif 대신 if를 써봤더니 답이 맞았네요.

즉, 어떤 6의배수가 들어오면 3으로 나눌 때가 더 최소경로일 수도, 2로 나눌 때가 더 최소 경로일 수도 있다고 생각해야 한다는 것인데

왠지 3으로 나누는게 더 이득일 것 같고, 직접 6, 12, 18, ... 테스트해보아도 3으로 나누는게 더 나쁘진 않습니다.

이해가 되지 않아서 반례를 직접 찾아보았더니 처음 2로 나누는 것이 3으로 나누는 것 보다 이득인 경우는 숫자 642인 경우였습니다.

그러므로 저 처럼 코드를 짰던 분은 642 가 반례가 될 수 있습니다.

642를 

3으로 나눈 214 : 최소거리 10

2로 나눈 321 : 최소거리 9

가 나와서 2로 먼저 나누는게 이득이네요.

elif가 왜틀려 라고 생각하시면 642 반례 대입해보시고...

개인적으로 642처럼 '혹시'2로 먼저 나누는게 더 최적인 숫자가 있을 수도 있다고 가정하는 것이 어렵네요..