글 읽기 - for문 관련 질문입니다.

rsmx 8년 전 0

안녕하세요,

문제를 푸는 도중에 의아한 점이 생겨 질문 드립니다.

다름이 아니라, 맵에서 상하좌우로 1칸씩 움직이는 것을 위해 아래처럼 배열과 for문을 이용하여 프로그램을 구현해보았습니다.

(1~9 Line)

허나, 이러한 방법으로 시행했을 땐, 1520번 문제에서 시간초과 걸리고 말았습니다.

이후, 이를 다음과 같이 풀어서 분기문만으로 고쳐본 결과 시간초과 없이 정상적으로 맞았다는 문구를 볼 수 있었습니다.

(12~25 Line)

제가 알기로는 이러한 방법이 틀리진 않는 것으로 알고 있는데 혹시 이것이 그렇게 시간 차이가 나는지 질문드립니다.

혹여 제가 잘못알고 있다거나 하는 등의 의견이 있으시면 알려주시면 감사하겠습니다.

감사합니다.

좋은 하루 되세요

int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
for (int d = 0; d < 4; d++){
        int r = row + dr[d];
        int c = col + dc[d];
        if (r >= 0 && r < M && c >= 0 && c < N  && map[r][c]<map[row][col]){
            func(r, c);
        }
    }

////////////////////////////////////////

if (row - 1 >= 0 && map[row - 1][col]<map[row][col]){
        func(row - 1, col);
    }

    if (row + 1<M && map[row + 1][col]<map[row][col]){
        func(row + 1, col);
    }

    if (col - 1 >= 0 && map[row][col - 1]<map[row][col]){
        func(row, col - 1);
    }
    if (col + 1<N && map[row][col + 1]<map[row][col]){
        func(row, col + 1);
    }

indioindio 8년 전 0

func함수에 side effect가 있고 그 side effect가 row-1, row+1, col -1, col +1순서대로 시행되었을 때 유리한 것 아닐까요

아래 이프 문이 비교횟수는 훨씬 적은데 800ms나 차이날지는 잘 모르겠네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

for문 관련 질문입니다.

rsmx 8년 전 0

indioindio 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말