인프런 커뮤니티 질문&답변
작성한 질문수
선생님 8-B,C 질문이요!
해결된 질문
작성
·
222
1
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
8-B의 해설에서 dp에서 상태값을 STR과 INT 이 두가지로 보고 있습니다. 방문한 요소들도 dp의 상태값에 있어야 한다 생각했는데 visited는 왜 영향을 주지 않는 변수로 둘 수 있는지 궁금합니다.
8-C도 마찬가지로 prev라는 변수가 dp의 상태값으로 쓰이지 않는 것에 대한 이유가 궁금합니다.
답변 1
1
안녕하세요 선우님 ㅎㅎ
DP는 단순하게 얘기하면 어떠한 배열을 만드는데 (map이 될 수도 있지만 보통은 배열) 이 배열에 문제에서 필요한 어떤 최적의 값이 들어가야 합니다. 그리고 또한.
보통의 dp를 정의하고 idx라는 변수가 들어가는 dp를 생각해보면 dp[idx]에는 이 idx일 때 ~~가 최적인 값이라는 의미가 담길 겁니다. dp[idx]는 갱신이 되어가며. 최적의 값이 해당 배열에 들어가는 샘이죠.
자 8 - B를 볼게요.
이 문제는 STR이 a이고 INT가 b일 때 최적의 값, 퀘스트갯수가 들어가야 하는 거 아닌가요? 즉, dp[str][int]에는 최대의 퀘스트 갯수가 들어가야 겠죠? 여기서 dp[str][int][visited]는 좀 이상합니다. 여기서 구하고자하는 것은 str, int가 무엇일 때 최적값인데 vistited가 더 들어가면 이상해집니다.
문제지문 : 준규가 깰 수 있는 퀘스트 개수의 최댓값을 구하는 프로그램을 작성하시오.
visited는 단순히 해당 퀘스트를 str, int에서 깼다면 방문처리하는 배열에 불과합니다.
만약. 선우님께서 비트마스킹을 생각해 넘기는게 어떠하냐? 라고 생각하시면 그건 맞습니다. (그래도 DP배열에 visited라는 3차원은 안만들어야 해요.) 그러나. 이 문제의 최대범위는 100이기 때문에 비트마스킹은 쓰지못합니다. 그렇기 때문에 무조건 vistied배열을 써야 하는 것이죠.
- 비트마스킹 강의 제가 업데이트 해놓았는데 업뎃본 안보셨다면 한번 봐주세요.
자, 8 - C를 볼게요.
일단 욱제는 각 파티션으로 만들어 놓은 배열의 요소들을 다 순회해야 하죠? idx가 필요합니다. 그리고 그 idx당 몇명의 친구를 쓸 수 있는지가 필요한 것이죠. num
따라서 dp[idx][num]을 정의해 해당 idx와 num일 때 최대시간을 담고 담아야 합니다. 여기서 prev는 앞선 함수에서 쓴 친구수이며 이 prev를 통해 지금 내가 친구를 정말로 몇명을 더 써야 하는지를 나타내는 거라. 이를 DP로 만드는 것은 불필요합니다.
다만, 이 8 - C의 경우는 dp[idx][num][prev]로 정의해서 만들수는 있을 거 같아요. 아마 go(0, k, 0, 0)으로 prev가 0부터 시작해서~~ 할 수 있겠죠. 그러나 비추합니다. DP할 때는 되도록이면 상태값을 많이 안만드는게 좋거든요.(배열 메모리, 해당 매개변수에 대한 비용, 개발자의 실수 줄임)
감사합니다.
아 그리고 담번엔 8 - C 문제에 질문하기 버튼 눌러서 질문하시면 제가 좀 더 보기 편해요. ㅎㅎ 그렇게 부탁드립니다.