작성한 질문수 4

0

안녕하세요 JL님 ㅎㅎ

    for (i = 0; i < N; i++) {
        if (solvable(STR, INT, i)) {
            // 방문처리
            if(visited[i] == 0) {
                visited[i] = 1; 
                visit.push_back(i);
                PNT += PNTs[i];
            }
        }
    }

    int nvisit = visit.size();
    ret = nvisit;

이부분에서 틀린 것 같습니다.

여기서 ret은 이 str, int일 때 처리할 수 있는 퀘스트개수를 의미해야 합니다.

여기서 해결가능하다면 -> ret을 ++를 하고 그 ret을 기점으로 해야하는데 지금 보시면 ret의 초기값이 visited에 맞춰져 있습니다. 저 부분은 해결가능하고 & 전의 str, int 상태로는 안깬 퀘스트를 의미해서 로직 자체가 어긋나게 되는 것 같습니다.

감사합니다.

int go(int STR, int INT) {
    int i;
    int PNT = 0;
    int ret;
    vector<int> visit; 
...

    for (i = 0; i < N; i++) {
        if (solvable(STR, INT, i)) {

0

안녕하세요, 인프런 AI 인턴입니다.

재귀 함수를 사용한 문제 해결 방식에서 틀린 점과 맞는 점을 비교해 보았을 때, 기본적으로 재귀함수를 호출하며 스텟이 바뀌고 그 결과를 통해 최대값을 갱신하는 로직은 같습니다. 하지만 틀린 풀이에서는 ret = max(ret, nvisit + go(STR + i, INT + (PNT - i))); 로 되어 있어 재귀 함수를 호출할 때마다 nvisit(새로 해결한 퀘스트 수)를 더하고 있습니다. 이는 현재 상태에서 해결할 수 있는 퀘스트 수를 재귀적으로 더해가며 카운트하는 방식으로 볼 수 있습니다.

반면, 맞는 풀이에서는 ret = max(ret, go(STR + i, INT + (PNT - i)));를 통해 스텟이 바뀔 때마다 새로운 퀘스트 수의 최대값을 직접적으로 비교하기만 합니다. 즉, 각 스텟 변화마다의 성공 횟수만을 반환하여, 그 중 최대값을 찾는 식으로 구현한 것이죠.

틀린 점은 재귀 함수의 호출과정에서 현재값(nvisit)을 더하는 처리를 한 것입니다. 이는 해당 재귀 단계에서 해결할 수 있는 퀘스트 수를 잘못 계산하게 만들 수 있습니다. 문제의 요구사항이나 재귀 함수 호출의 논리에 따라 이런 방식이 오히려 문제의 답을 찾는 데 방해가 될 수 있습니다. 재귀 함수의 기본 원리와 문제의 요구 사항을 정확히 이해하고, 각 단계에서의 반환 값과 그 의미를 명확히 하는 것이 중요합니다.

재귀 함수와 dp를 활용한 문제 해결에서는 각 단계에서 어떤 값을 반환하고, 이를 어떻게 활용할지에 대한 정확한 이해가 필요합니다. 문제의 조건과 목표를 명확히 파악하고, 각 재귀 호출이 의미하는 바를 정확히 이해하면서 문제를 접근해야 합니다.

항상 강의에 집중해주셔서 감사합니다. 앞으로도 코딩 테스트 준비에 도움이 되는 내용을 제공해드리기 위해 노력하겠습니다.