[질문] 백준 오픈콘 H번(초전도체) 틀린 이유가 뭐였을까

[익명(125.191)]

n!=h일때 큰 덩이 1조각/1g짜리 h-1조각으로 나누는 게 답일 것 같아서 dp로 풀었는데 틀렸습니다 나옴

반례가 있었나? 아님 처음부터 발상을 잘못한 건가?

[익명(211.57)]

그렇게 자르는게 맞는거같고 조각을 합칠때 원래는 우선순위 큐로 가장 작은거 두 개를 계속 합쳐나가는 방식으로 답을 구하는데 개수가 많아서 수학으로 밀어야하는듯 나도 어케하는진 모름

[익명(125.191)]

난 n개를 n개의 조각으로 나눌 때엔 그 조각을 반으로 나누고->다시 그 조각을 반으로 나누고....를 조각의 길이가 1이 될 때까지 반복하는 게 답일 거라 생각해서 탑다운으로 했었음. 근데 시간초과가 아니라 틀렸습니다를 받더라고. 탑다운으로 했을 때 생기는 오류가 있었을까?

[익명(14.49)]

그렇게 나누는게 이득일 때도 있고 1/2씩 나누는게 이득일 때도 있음 16 15 생각해보셈

[익명(14.49)]

근데 나도 틀림 뭐에서 틀린건지는 모르겠다

[익명(14.49)]

너가 한 방법대로 하면 아마 16 15가 70이 나올거임 근데 아마 62가 답일거임 내가 한게 맞다면

[익명(125.191)]

맞네 내 프로그램에선 70 나옴 방법이 틀려먹었었구나

[익명(14.49)]

근데 ㅅㅂ 나도 틀려서 K하나 풀고 H에서 맞왜틀 3시간동안 함 ㅋㅋㅋ 더 무서운건 난 왜틀린지도 모른다는거임 ㅋㅋㅋ

[익명(125.191)]

넌 대충 어떤 식으로 풀었음?

[익명(14.49)]

너가 한 방법으로 답 구하고 2개씩 비슷한 크기로 계속 나누는거로 답 구해서 더 작은 값 출력

[익명(125.191)]

반례 n=18, h=13인 듯? 아마 너 방법대로 하면 9(9)+9(4)로 나눠서 61 나올 것 같은데 10(5)+8(8)로 나누면 60으로 줄일 수 있음

[익명(14.49)]

헐 그런 경우도 있냐 고맙다