인프런 커뮤니티 질문&답변
작성한 질문수
7-Y 질문드립니다.
해결된 질문
작성
·
9
0
안녕하세요. 7-Y 바텀업 풀이방식에서 의문점이 생겨 질문드립니다.
의문이 생긴 부분은 dp[i]와 dp[i - a[j]] + to_string(j)를 비교하면서 더 작은 걸로 업데이는 하는 과정인데요, 저도 풀었을 때 이렇게 풀었으나 다시 보면서 생각해보니, j를 뒤에 붙인 dp[i-a[j]] + to_string(j)뿐만 아니라 기존 문자열에 앞에 j를 붙인 to_string(j) + dp[i-a[j]]와도 비교를 해줘야 될 것 같아서요.
to_string(j) + dp[i-a[j]]가 최소가 되지 못하는 이유가 있어서 풀이가 맞다고 나온것일텐데 이류를 생각해봐도 선뜻 생각이 나지 않네요..ㅜㅜ
j를 뒤에다가 붙인 경우만 확인해도 되는 이유가 무엇인가요??
답변 2
0
안녕하세요 예찬님 ㅎㅎ 이부분 말씀하시는거죠?
dp[i] = get_min_str(dp[i], dp[i - a[j]] + to_string(j));여기서 dp[i - a[j]] + to_string(j) 이부분을 to_string(j) + dp[i - a[j]] 이렇게 하면 왜 안되느냐? 라는 질문인것 같은데요.
dp[i] 는 “만들 수 있는 가장 작은 수”를 문자열로 저장해둡니다.
여기서 만약 to_string(j) + dp[i - a[j]] 이런식으로 가게 되면
지금까지 만든게 11, 12 따위의 작은 수인데 갑자기 앞에다가 2 + 11, 1 + 12 이런식으로 붙여서 비교하게 되는 거라 지금까지 만든 “만들 수 있는 가장 작은 수”의 의미가 사라지는 경우의 수가 생겨버리기도 해서 dp의 의미자체가 깨져서 안될 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 예찬님 ㅎㅎ
먼저 예찬님 말씀이 맞습니다.
첨언을 하면 다음과 같습니다.
dp[i] = get_min_str(dp[i], to_string(j) + dp[i - a[j]]);예를 들어 앞의 코드의 경우 dp[14] = 88이 되지만 dp[16] = 004가 됩니다.
즉, 맨 앞자리가 0이 아니어야 한다하는 조건때문에 이러한 코드가 안되는 것이죠.
자 그렇다면 바텀업으로 앞의 코드를 살려서 진행한다고 해봅시다.
if (j == 0 && dp[i - a[j]] == "") continue;이런식으로 맨앞자리는 0이 아니어야 하는 규칙을 넣어서 진행을 하겠죠?
하지만 여기서 문제가 발생하는게 104와 같은 수가 만약 최저값이라면 해당 수는 만들지를 못합니다. 저 코드자체가 04 자체를 만들지 못하고 -> 그 이후에 104를 만들지 못하기 때문입니다.
이러한 로직상 한계 + 문제조건 때문에 더더욱 해당부분이 안되는 것같습니다.
혼란을 줘서 죄송하다는 말씀을 드립니다.
이런 경우가 거의 없는데
요새 일이 바빠서 실수가 잦네요.. ㅠㅠ
또한,
예찬님처럼 “단순히 제가 그렇게 얘기했으니까 넘어가지 않고” 이렇게 물어보시는 것은 좋은 습관입니다.
계속해서 부담갖지 말고 질문주세요. ㅎㅎ
0
안녕하세요, 인프런 AI 인턴입니다. 문예찬님.
질문해주신 바텀업 방식의 동적 프로그래밍(DP) 풀이에서 숫자를 뒤에 붙이는 방식에 대해 설명드리겠습니다.
DP에서의 숫자 조합
이 문제에서 우리는 성냥개비를 사용하여 숫자를 만들어야 합니다. 숫자 조합의 경우:
- dp[i]는 현재 사용된 성냥개비 수 i로 이루어진 최소 숫자 문자열을 의미합니다.
우리가 관심을 가지는 점은 j를 숫자 문자열로 변환하여 그 후에 붙일지, 혹은 앞에 붙일지의 선택입니다.
뒤에 붙이는 이유
숫자가 작을수록 앞에 오는 숫자 우선: 일반적으로 작은 문제(greedy)에서 더 작은 숫자가 앞쪽에 오는 경우 숫자 값이 최소화됩니다. 그 경우 뒤쪽에 붙여도 최소값이 생기는데 유리하게 작용할 수 있습니다.
정렬적 관점에서의 유리함: 특정 조건에서는 작은 숫자를 지속적으로 뒤로 추가함으로써 불필요한 연산을 줄이고도 최소값을 얻는 결과를 유지합니다.
구현의 용이성: 주어진 알고리즘 설계대로 할 때 더 큰 숫자부터 탐색을 시작하여 큰 차이 없이 모든 경우에서 최소화할 수 있는 장점을 가집니다.
해당 문제 설정에서는 이 방식이 효율적인 이유로 작용하며, 문제 설정 및 제약에 따라 숫자배열의 조작을 통해 최적의 값을 얻기 위해 그리디 방식으로 뒷부분에서 붙인 형태로 설계되었다고 볼 수 있습니다.
비슷한 문제 풀이가 있는 링크로 추가적인 설명을 참고하시면 도움이 될 수 있습니다:
- 수열 문제와 최적화 고민
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 감사드립니다.
질문을 올린 뒤에도 생각해보고 큰돌님 답변을 읽은 후에도 생각해본 결과 제 생각은 좀 다른 것 같아서 제 생각을 말씀드려보겠습니다.
큰돌님께서 dp[i]의 의미인 성냥개비 i개로 만들 수 있는 가장 작은 수라는 의미가 사라질 수도 있다고 말씀하셔서 그걸 중심으로 다시 생각해봤습니다. 성냥개비 i개로 만들 수 있는 수는 무조건 그리고 당연하게도 0 ~ 9, 10개의 숫자중 하나로 끝나게 됩니다. 그리고 각 끝나는 숫자에 대해서 그 앞에 오는 수는 끝에 오는 숫자를 성냥개비로 만들고 남은 성냥개비(i-a[j]개)로 만드는 숫자 중에 가장 작아야 하고 그 수가 바로 dp[i-a[j]]입니다. 그래서 j = 0 ~ 9에 대해서 dp[i-a[j]] + to_string(j)중 가장 작은 값이 dp[i]가 되는게 확실하고 모든 경우를 커버했기 때문에 이런식으로 to_string(j)를 뒤에다 붙이는 방식이 당연히 앞에다 붙이는 방식을 커버하게 됩니다. to_string(j) + dp[i-a[j]]가 "만들 수 있는 가장 작은 수"의 의미가 사라지는 건 아닙니다.
저를 헷갈리게 했던 예시를 들면서 말씀드려보겠습니다.
dp[16]을 구한다고 생각해보겠습니다. (i = 16) 그리고 j = 1이 맨 뒤에 오는 경우를 생각해볼게요. a[j] = a[1] = 2이고 dp[i-a[i]] = dp[16-2] = dp[14] = "88"입니다. 이 때 "1"을 뒤에 붙이면 "881"이 되니까 차라리 "1"을 앞에 붙여서 "188"을 만들어서 dp[16]과 비교해서 업데이트 하는게 더 나을수도 있겠다는 생각을 했습니다. 그래서 "1"을 뒤에다 붙이는 경우, 앞에다 붙이는 경우를 둘 다 생각해야 한다고 생각했습니다.
하지만 앞서 말했듯이 dp[i-a[j]] + to_string(j)로 확인하는 방식이 모든 경우를 커버해야합니다. "188"의 경우 "8"로 끝나는 경우를 확인할 때 커버하겠죠. j = 8인 경우니까 이때 dp[i-a[j]] = dp[16-a[8]] = dp[16-7] = dp[9] = "18"에 "8"을 뒤에 붙여 dp[16]과 비교하여 업데이트 하게됩니다. "188"을 커버하게 됐죠. 이때 8로 끝나는 숫자중에 가장 작은 값("188")을 확인할 때 아까 확인해야 되나 싶었던 1로 시작하는 가장 작은 값을 커버하게 되죠. 이 경우에는 1로 시작하는 가장 작은값과 8로 끝나는 가장 작은 값이 같았지만 꼭 같지는 않습니다. 하지만 8로 끝나는 숫자가 항상 같거나 더 작을 것입니다. (이 이유에 대해서까지 적으면 길어질 거 같아서 넘어가겠습니다.)
사실 같은 원리로 to_string(j) + dp[i-a[j]]방식도 모든 케이스를 커버할 수 있어야 합니다. 하지만 이 문제에서는 "맨 앞자리가 0이 아니어야 한다"는 조건 때문에 이 방식을 쓰지 못합니다. 앞자리에 숫자를 붙여나갈 때 맨 앞자리가 0이면 안 된다는 조건 때문에 0을 붙이지 못하고 자릿수가 하나일 때부터 차곡차곡 숫자를 붙여나가면서 dp를 업데이트 해 나가는 과정에서 어느 순간에도 앞에 0을 붙이지 못하기 때문에 dp[i-a[j]]에 0이 항상 포함되지 못하게 됩니다.
맨 앞자리가 0이면 안된다는 조건이 없다면 두 방식 모두 같은 결과를 냅니다.
http://boj.kr/dc2685eb6157415ab054146da368d8a9
위 링크의 코드는 제가 원래 냈던 코드인데 맨 처음에 minDp의 기저사례 (한 자릿수) 초기화 할때는 자릿수가 하나인 경우라서 i가 0이 아닌 1부터 루프를 돌지만 아래에 minDp를 계속 바텀업으로 업데이트 할 때는 i = 0을 포함해서 루프를 돌립니다.
하지만 맨 앞자리가 0이면 안된다는 조건이 없거나 (http://boj.kr/358f7f3f4b7845648616ff123967caa2)
모든 자릿수에 0이 오면 안된다는 조건이라면 (http://boj.kr/020b1503f0bd43dea2372dd55786d22c)
제 코드에서 minDp와 minDpReverse는 완전히 같은 결과를 냅니다. (여기서 minDp는 dp[i-a[j]] + to_string(j)의 뒤에 붙이는 방식, minDpReverse는 to_string(j) + dp[i-a[j]]처럼 앞에다 붙이는 방식)
그래서 to_string(j) + dp[i - a[j]]이 안되는 이유는 "만들 수 있는 가장 작은 수"의 의미가 사라진다는 것보다는 "맨 앞에 0이 올 수 없다"는 조건에 맞지 않다는 설명이 더 맞다고 생각합니다.
어쩌다보니 큰돌님께서 답변을 주실 때마다 제가 제 생각은 이렇다고 주제넘게 반박하게 되는 듯한 기분이 드는데 절대 큰돌님에게 따지려고 그런건 아닙니다. 하지만 어째 제가 질문을 남기고나서야 질문에 대한 답을 결론내릴 수 있게 돼고 그 결론이 종종 큰돌님 답변과 달라서 그렇게 된 것 같습니다. 큰돌님이 항상 친절하게 답변해주시는 점 항상 감사드립니다.