인프런 커뮤니티 질문&답변

JL님의 프로필 이미지
JL

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

8-B 문제 문의

해결된 질문

작성

·

129

·

수정됨

1

안녕하세요 선생님,

8-B 문제에 대해 문의드리고 싶습니다.

저는 재귀를 들어갈 때 마다 (스텟이 바뀔 때 마다) 새로 해결한 퀘스트 수를 더하는 식으로 문제를 풀었는데 틀렸습니다. 저는 dp를 풀 때 현재값 + 재귀값으로 풀어왔는데 틀리니 이상합니다.

48번 줄: ret = max(ret, nvisit + go(STR + i, INT + (PNT - i)));

 

선생님 풀이를 보고, 각 재귀 마다 현재 스텟에서 성공한 횟수를 반환하는 식으로 구현하니 맞게 나옵니다.

47번 줄: ret = max(ret, go(STR + i, INT + (PNT - i)));

 

선생님 풀이와 로직은 동일한 것 같은데, 어떤 부분에서 틀렸는 지 모르겠습니다.

 

틀린 풀이

https://www.acmicpc.net/source/share/9878747de0af458ca79dde4f3555903c

맞는 풀이

https://www.acmicpc.net/source/share/e7061d5e24564ad2a773395440381ecc

 

항상 강의 잘 듣고 있습니다.

감사합니다.

답변 2

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 상태로는 안깬 퀘스트를 의미해서 로직 자체가 어긋나게 되는 것 같습니다.

감사합니다.

JL님의 프로필 이미지
JL
질문자

안녕하세요 선생님,

답변 감사드립니다. 다시 한 번 고민하도록 하겠습니다.

감사합니다.

JL님의 프로필 이미지
JL
질문자

안녕하세요 선생님,

로직에 대해 다시 문의드리고 싶습니다. 저는 제가 작성한 로직과 선생님께서 작성하신 로직이 동일하다고 생각됩니다.

지금 해결한 퀘스트 수 + 다음에 해결할 퀘스트 수 = 다음 스텟으로 해결할 수 있는 퀘스트 수

 

그래서 저는 방문처리를 이용하여 이전에 해결한 퀘스트를 제외하고, 지금 해결한 퀘스트를 세고 (nvisit), 다음 재귀에서 새로 해결한 퀘스트 (go(STR + i, INT + (PNT - i)))를 더 해주는 방식으로 코드를 구현했습니다.

48번 줄: ret = max(ret, nvisit + go(STR + i, INT + (PNT - i)));

 

다시 한 번 확인해주시면 감사하겠습니다.

감사합니다.

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 JL님 ㅎㅎ

그래서 저는 방문처리를 이용하여 이전에 해결한 퀘스트를 제외하고, 지금 해결한 퀘스트를 세고 (nvisit), 다음 재귀에서 새로 해결한 퀘스트 (go(STR + i, INT + (PNT - i)))를 더 해주는 방식으로 코드를 구현했습니다.

>> 근데 이러면 지금의 STR, INT를 기반으로 해결하는 퀘스트 수는 안세게 되지 않을까요?

지금 해결한 -> 이라는 의미가

지금의 STR, INT로 해결할 수 있는 퀘스트 - 이전 타임에서 해결한 퀘스트

가 되는데요.

이렇게 되면 DP의 의미인 STR, INT로 해결할 수 있는 퀘스트 수라는 의미가 깨지지 않나요?

 

그니까 이 DP의 의미는 매개변수가 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)) {

그래서 여기서 현재 STR, INT를 기반으로 깰 수 있는 퀘스트수를 구하려면 STR, INT받고 -> 해결가능하다면 -> 카운팅을 한 해당 값을 기반으로 해야 하는 것 아닌가요?

 

감사합니다.

JL님의 프로필 이미지
JL
질문자

안녕하세요 선생님,

친절한 답변 감사합니다. 다시 고민하도록 하겠습니다.

감사합니다.

0

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

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

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

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

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

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

JL님의 프로필 이미지
JL

작성한 질문수

질문하기