2240번 자두나무 질문있씁니다!

작성한 질문수 6

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.