인프런 커뮤니티 질문&답변
작성한 질문수
7-Y 성냥개비 문제 최소값을 Top-Down으로 풀었을 때 질문이 있습니다
작성
·
108
·
수정됨
0
안녕하세요, 큰돌님 강의 열심히 듣고 있는 수강생입니다.
제 풀이입니다. 사실상 강의 코드와 거의 일치합니다.
(다른 점은 올 수 있는 숫자 중 필요 성냥개비 수가 같은 수 중 큰 수를 제거하고 0,1,2,4,6,7,8 에 대해서만 따로 배열을 만들어 돌렸다는 정도입니다)
https://www.acmicpc.net/source/79322370
강의 내용을 바탕으로 바텀업 방식과 탑다운 방식으로 모두 풀어보았는데요.
문제 해설에 남겨주신 풀이도 바텀업인 것을 보니 이 문제의 정통 풀이법은 아마 바텀업인 것 같습니다.
탑다운 방식의 풀이가 틀린 것은 아닌데..
테스트 케이스가 여러 개 주어지는 문제이다보니 성냥개비 개수를 작은 순으로 (4개, 7개, 10개..) 주면 맞는데, 처음 주어지는 성냥개비 개수가 큰 경우(예를 들어 100개부터 주어지는 경우) 에는 100개에 대한 top-down을 돌면서 거쳐온 중간 값들을 dp에 저장하는데 이때 '첫째 자리에는 0이 올 수 없다' 라는 조건을 만족하지 못하는 수가 다수 저장됩니다.
입력으로 주어진 수 x에 대해서는
if (left == x && num == 0) continue;
해당 구문으로 첫째 자리에 0이 오는 것을 방어하는데, 이후 입력으로 받은 수가 dp 테이블에 기록되어있다면 바로 return해버려서 되다 만 중간값을 그냥 반환해버리는 문제가 있는 것 같습니다.
그렇다고 모든 입력에 대해 dp테이블을 전부 비웠다가 다시 탑다운으로 일일이 계산하는 것은 너무나 비효율적같아 보이는데.. 이렇기 때문에 이 문제 풀이는 바텀업이 정배(?)인건가요?
아니면 탑다운 방식에서 제가 뭘 놓치고 있는 것이 있을까요?
답변 1
0
안녕하세요 레페님ㅎㅎ
문제 해설에 남겨주신 풀이도 바텀업인 것을 보니 이 문제의 정통 풀이법은 아마 바텀업인 것 같습니다.
>> 음.. 아닙니다. 둘 다 남겨놨어요!!
findMin을 탑다운으로 푸는 방법은 다음과 같습니다.
http://boj.kr/21b4548a1caa47458176414e1bf3d2fe
string findMin(int here){
if(here == 0) return "";
string &ret = dp[here];
if(ret != MAX_STR) return ret;
for(int i = 0; i <= 9; i++){
if(here - a[i] < 0) continue;
if(here == n && i == 0) continue;
ret = get_min_str(ret, to_string(i) + findMin(here - a[i]));
}
return ret;
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
헉 문제해설집에 답 코드가 두개 있는지 몰랐네요. 감사합니다.
큰돌님의 탑다운 코드에서도 바텀업 코드와는 다르게 매 입력마다 dp테이블을 초기화해주고 있는데, 아무래도 탑다운으로는 바텀업처럼 최대치까지 다 채워놓고 이후에 들어오는 입력에 해당하는 수만 출력하는 방식은 불가능한 것 같네요ㅜㅜ