3-O 15684 사다리조작 질문입니다.

안녕하세요.

해설 코드 중에 질문이 있습니다.

go 함수에서

void go(int here, int cnt)
{
    if (cnt > 3 || cnt >= ret)
        return;
    if (check())
    {
        ret = min(ret, cnt);
        return;
    }
    for (int i = here; i <= h; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1])
                continue;
            visited[i][j] = 1;
            go(i, cnt + 1);
            visited[i][j] = 0;
        }
    }
}

for (int j = 1; j < n; j++)

j 에 대한 for문을 제 생각에는 n을 포함하지 않아야 한다고 생각합니다. 그렇게 돌리면 정답으로 처리가 되기도 하고요. 그런데 n을 포함하면 N번째 세로선에서 오른쪽으로 이동하는 가로선이 추가될 수 있는건데 실제로 그렇게 추가할 수 없잖아요? 그럼에도 불구하고 n을 포함하여 코드를 실행해도 왜 정답처리 되는건지 궁금증이 생겼습니다.

예를 들어 가능한 반례로써 for문에서 j = n 인 경우 N번째 세로선과 가상의 N+1 번째 세로선 사이에 가로선이 2개만 추가되어도 check에서 true를 반환할 것인데 이런 반례가 존재하는 경우는 전부 가로선을 전혀 추가하지 않아도 되는 경우뿐이라 cnt = 0에서 바로 끝나서 그런게 아닌가 합니다. j 를 n보다 큰 수 까지 가능하게 범위를 설정해서 돌리면 실제로 틀리지는 않고 시간초과만 뜨긴 합니다.

결과적으로 j = n 까지 가능하게 하는것이 답을 계산하는데는 틀리지는 않지만 조금 비효율적이지 않나 싶습니다. 이론적인 실제 범위인 j를 n - 1까지로 설정하면 시간이 33%정도 줄어들기도 하고요.

이부분에 대해 어떻게 생각하시는지 질문드립니다.

안녕하세요 ㅎㅎ

결과적으로 j = n 까지 가능하게 하는것이 답을 계산하는데는 틀리지는 않지만 조금 비효율적이지 않나 싶습니다. 이론적인 실제 범위인 j를 n - 1까지로 설정하면 시간이 33%정도 줄어들기도 하고요.

>> 네 맞습니다. 이렇게 하는게 더 효율적인 것같습니다. 예리하십니다...

    for(int i = here; i <= h; i++){
        for(int j = 1; j < n; j++){
            if(visited[i][j] || visited[i][j - 1] || visited[i][j + 1]) continue;
            visited[i][j] = 1;
            go(i, cnt + 1);
            visited[i][j] = 0;
        }
    }

테스팅해봤는데 400ms 정도 차이가 나는 것 같습니다.

해당 부분은 오늘내로 반영하도록 하겠습니다.

그럼에도 불구하고 n을 포함하여 코드를 실행해도 왜 정답처리 되는건지 궁금증이 생겼습니다.

>> 애초에 배열의 범위자체를 좀 더 크게 설정했고 -> 오버플로 제거 / check() 함수같은 경우 n + 1 부분을 체크하지 않기 때문에 정답처리는 되는 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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