i가 !(i%3) && !(i%2) 일떄
dp[i-1]+1 > dp[i/2]+1 > dp[i/3]+1이라면?
dp[i]에 저장 되야하는 값은 dp[i/3]+1이지만 dp[i/2]+1의 값이 저장됩니다.
1463번 - 1로 만들기
안녕하세요!
질문자님께서 작성하신 대로, 본 문제에서는 dp[i]가 최적인 값을 구하는 방법은 아래의 1), 2), 3) 중 최솟값이 맞습니다.
1) dp[i - 1] + 1 2) i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1 3) i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1
틀린 이유는 질문자님의 코드에서는 이 3가지 경우를 모두 비교하고 있지 못 해서인 것 같습니다. 점화식 부분을 한 번 볼까요?
dp[i] = dp[i-1]+1;
⇑ dp[i] 값에 우선 1) 의 경우를 최적값으로 저장했습니다. 여기까지는 제대로 하셨습니다. 이제 2), 3)의 경우와도 비교해 주시면 됩니다.
if(!(i%3)) dp[i] = min(dp[i-1]+1, dp[i/3] + 1);
⇑ 1) 의 경우와 3) 의 경우 중 최적값으로 저장하는 점화식입니다.
if(!(i%2)) dp[i] = min(dp[i-1]+1, dp[i/2] + 1);
⇑ 1) 의 경우와 2) 의 경우 중 최적값으로 저장하는 점화식입니다.
그러면, 이 점화식에서 만약 1) 보다 2) 인 경우가 최적이고, 2) 보다 3) 가 더 최적인 경우가 주어지면 어떻게 될까요?
2) 인 경우와 3) 인 경우 중 어느 쪽이 최적인 지를 비교하는 점화식이 없으니, 3) 이 더 최적인 경우에도 2) 가 최적인 경우로 덮어씌워지는 경우가 생길 수 있겠죠? 코드에서 2) 인 경우와 3) 인 경우를 비교하는 점화식이 필요합니다.
저는 dp[i - 1] + 1 부분을 그냥 dp[i] 로 변경하여 해결했습니다. 이유는 제가 코드로 첨부해서 알려드리고자 합니다.
문제 해결에 도움이 되었기를 바랍니다!
!(i%3) && !(i%2)일 때
min(dp[i/3] + 1, dp[i/2] + 1, dp[i -1] +1)으로 작동되야 하는데
제 코드는 그렇게 작동 안되서 틀리는 거군요.
감사합니다!! 매우 명쾌합니다!!
혹시 2)가 3)보다 최적인 경우의 예를 알 수 있을까요?
2)가 3)보다 최적인 예로 642를 들 수 있습니다.
2)가 3)보다 최적임을 증명하기 위해, 처음에 642를 1로 바꾸기 위해 첫 번째 연산을 할 때만 각각 2, 3으로 나누고, 그 다음 연산부터는 3가지의 연산을 모두 고려한 최적값을 구하는 연산대로 해 봅시다.
입력: 642 1. 처음에 2로 무조건 나누고, 그 다음부터는 최적의 방법대로 642 --무조건 2로 나누기--> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1 총 10번의 연산 필요 2. 처음에 3으로 무조건 나누고, 그 다음부터는 최적의 방법대로 642 --무조건 3으로 나누기--> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 3 -> 1 총 11번의 연산 필요
따라서, 경우에 따라서는 2와 3으로 모두 떨어지는 수라도 2로 나누는 게 더 최적일 수도 있습니다. 그러므로 항상 3가지의 연산을 모두 고려해 줘야 정답을 받는다고 할 수 있겠습니다!
신기하네요! 정말 친절한 답변에 감동 받아갑니다:)
좋은 하루 되세요! 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
hellowfriend 4년 전 1
for(int i =2; i<= N; i++){
dp[i] = dp[i-1]+1;
if(!(i%3)) dp[i] = min(dp[i], dp[i/3] + 1);
if(!(i%2)) dp[i] = min(dp[i], dp[i/2] + 1);
}
위의 코드를 제가 아래의 코드와 같이
for(int i =2; i<= N; i++){
dp[i] = dp[i-1]+1;
if(!(i%3)) dp[i] = min(dp[i-1]+1, dp[i/3] + 1);
if(!(i%2)) dp[i] = min(dp[i-1]+1, dp[i/2] + 1);
}
바꾸었는데
틀렸습니다.라고 하네요.
이유를 아시는 분은 알려주시면 정말 감사하겠습니다.
좋은 하루 보내세요!