인프런 커뮤니티 질문&답변
작성한 질문수
2240번 자두나무 질문있씁니다!
작성
·
370
0
안녕하세요 선생님! 제가 이해하는 것이 맞나 싶어서 여쭤보고자 질문올립니다!
Q1.
밑에 이부분에서는 go(0,1,m-1)같은 경우와 go(0,0,m)는 완탐 시 처음 시작하자마자 움직이는 경우에 수를 나누어서 쭉쭊죾 한다음에 max값을 찾기 위해 구현한 것이 맞을까요?
cout << max(go(0, 1, m - 1), go(0, 0, m)) << '\n'; Q2.
밑에 이 부분에서 ret을 참조자로 받아서 반환하는 이유가 혹시 있을까요? 참조자를 사용하지 않으면 시간초과가 나더라구요.. 참조자를 통해서 직접 적으로 dp배열의 값을 참조하면 메모리를 효율적으로 쓸수 있어서 그런건가여? 근데 또 궁금하게 int &ret을 계속 생성하는건데.. 조금 햇갈립니다..ㅠ
int &ret = dp[idx][tree][cnt]; if(~ret) return ret; Q3.
이 부분은 현재의 index에서 다음 인덱스로 갈떄 옆에 트리로 가는경우 안가는경우나눠지는 것으로 해석하였습니다. 그런데 뒤에 go함수 같은경우는 나무이동을 안할떄로 알고 있씁니다. 뒤에 (tree ==b[idx]+1) 같은 경우는 다음 go로 넘어가기 전 현재의 위치에 tree와 그 시간대 tree에 위치가 같으면 +1 (idx시간 떄 자두를 받았기 떄문) 아니면 0을 더하는 것 이 맞나요?!?
return ret = max(go(idx + 1, tree^1, cnt - 1), go(idx + 1, tree, cnt)) + (tree == b[idx] - 1);Q4. 이건 문제와 외람된 말이긴 합니다. 지금 매 주차 개념설명 들으며 2~3문제 씩 주차 문제 풀면서 다음 주차 개념을 빠르게 듣고 있습니다. 과정이 너무 어려운데 이해가 안되면 문제를 외우기보다는 그 과정이 어떤식으로 대처해야하는지 위주로 공부하고 있습니다. 잘하고있는걸까여ㅠ,,
퀴즈
동적 계획법(Dynamic Programming)을 적용하기 위한 주요 조건은 무엇일까요?
탐욕적 선택 속성, 최적 부분 구조
최적 부분 구조, 중복되는 부분 문제
중복되는 부분 문제, 결정론적 결과
탐욕적 선택 속성, 메모이제이션
답변 1
0
안녕하세요 상우님 ㅎㅎ
7 - D 2240이시죠?
Q1.
밑에 이부분에서는 go(0,1,m-1)같은 경우와 go(0,0,m)는 완탐 시 처음 시작하자마자 움직이는 경우에 수를 나누어서 쭉쭊죾 한다음에 max값을 찾기 위해 구현한 것이 맞을까요?
>> 네 맞습니다. 처음에 문제를 보시면...
자두는 1번 자두나무 아래에 위치해 있다고 한다.
이렇게 되어있죠? 여기서 내가 빠르게 후다다닥 움직여서 2번으로 가는지, 1번으로 가는지 거기서 부터 시작해서~ 경우의 수를 구한다고 보시면 됩니다.
밑에 이 부분에서 ret을 참조자로 받아서 반환하는 이유가 혹시 있을까요? 참조자를 사용하지 않으면 시간초과가 나더라구요.. 참조자를 통해서 직접 적으로 dp배열의 값을 참조하면 메모리를 효율적으로 쓸수 있어서 그런건가여? 근데 또 궁금하게 int &ret을 계속 생성하는건데.. 조금 햇갈립니다..ㅠ
>> 저거 dp쓰기가 너무 귀찮아서 그런거에요. ret을 안쓰셔도 됩니다. 이렇게 하셔도 됩니다.
저거 근데 &을 쓰는 이유는 = 참조로 걸어야 ret을 수정해도 원본배열이 수정되니 참고해주세요. ㅎ
#include<bits/stdc++.h>
using namespace std;
int dp[1004][2][34], n, m, b[1004];
int go(int idx, int tree, int cnt){
if(cnt < 0) return -1e9;
if(idx == n) return cnt == 0 ? 0 : -1e9;
if(~dp[idx][tree][cnt]) return dp[idx][tree][cnt];
return dp[idx][tree][cnt] = max(go(idx + 1, tree^1, cnt - 1), go(idx + 1, tree, cnt)) + (tree == b[idx] - 1);
}
int main(){
memset(dp,-1,sizeof(dp));
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> b[i];
cout << max(go(0, 1, m - 1), go(0, 0, m)) << '\n';
return 0;
}
go함수 같은경우는 나무이동을 안할떄로 알고 있씁니다. 뒤에 (tree ==b[idx]+1) 같은 경우는 다음 go로 넘어가기 전 현재의 위치에 tree와 그 시간대 tree에 위치가 같으면 +1 (idx시간 떄 자두를 받았기 떄문) 아니면 0을 더하는 것 이 맞나요?!?
>> go함수는 2개의 경우의 수를 다 진행합니다. 이동 또는 이동하지 않느냐. idx + 1을 하면서. 저 + 는 여기서 이 정점에서의 자두위치가 같으면 1을 더한다고 보시면 됩니다.
Q4. 이건 문제와 외람된 말이긴 합니다. 지금 매 주차 개념설명 들으며 2~3문제 씩 주차 문제 풀면서 다음 주차 개념을 빠르게 듣고 있습니다. 과정이 너무 어려운데 이해가 안되면 문제를 외우기보다는 그 과정이 어떤식으로 대처해야하는지 위주로 공부하고 있습니다. 잘하고있는걸까여ㅠ,,
>> 아뇨 개념 -> 해당 개념 주차 다 풀어주세요. 개념은 문제풀이로써 정립됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.