sm0819   2년 전

시간초과 자꾸 뜨는데 뭐가 문젠가요 ㅠㅠㅠㅠㅠ

여기 예제는 다되던데...

19
3 2
100 100 100
1 2
2 3
1
3 2
100 100 100
1 2
2 3
2
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
3
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
4
11 10
10 100 1 1 1 5 8 9 7 1000 10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
10 11
11 3
6
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7
10 11
10 1 1 100 10 10 100 1 1 1
1 2
2 3
3 6
4 3
4 7
4 9
5 4
6 9
7 8
8 9
10 7
9
5 4
10 1 100 10 1000
5 2
1 3
2 4
3 4
4
7 6
1 100 10 1000 10 1 1
1 2
2 3
3 7
4 5
5 6
6 7
7
7 6
1 10 1 100 1 5 8
1 2
2 3
4 5
5 3
3 6
3 7
3
7 6
1 10 1 100 1 5 8
1 2
2 3
4 5
5 3
3 6
3 7
7
5 3
1 3 10 10 5
1 4
2 3
3 5
2
5 3
1 3 10 10 5
1 4
2 3
3 5
3
5 3
1 3 10 10 5
1 4
2 3
3 5
5
5 3
1 3 10 10 5
1 4
2 3
3 5
4
5 3
1 3 10 10 5
1 4
2 3
3 5
1
2 1
10
5
2 1
2
2 1
10
5
2 1
1


evenharder   2년 전

n=6일 때 다음과 같은 test case를 생각해봅시다.

1
6 15
1 1 1 1 1 1
5 6
4 6
4 5
3 6
3 5
3 4
2 6
2 5
2 4
2 3
1 6
1 5
1 4
1 3
1 2
6

dfs 함수의 흐름을 따라가면 다음과 같습니다.

- dfs 처음에 다음 함수를 추가하였습니다.

for(int i=0;i<N-n;i++)
        printf("--");
    printf("%d\n",n);

6
--5
----4
------3
--------2
----------1
----------1
--------2
----------1
----------1
------3
--------2
----------1
----------1
--------2
----------1
----------1
----4
------3
--------2
----------1
----------1
--------2
----------1
----------1
------3
--------2
----------1
----------1
--------2
----------1
----------1

6이 1번, 5가 1번, 4가 2번, 3이 4번, 2가 8번, 1이 16번 나오게 됩니다(왜 이렇게 나오는지는 한 번 생각해보세요).

호출횟수를 세면 32번, 즉 2^5입니다. 2^(n-1)이랑 같죠. n = 30 정도만 되어도 계산하는데 몇 초는 걸립니다. 하물며 n=100이면 어떻게 될까요.

이는 dfs에서 계속 중복 호출이 일어나서 발생하는 문제이므로, bfs로 한 번 해보세요.


Test case generator Python3 코드도 첨부합니다.

sm0819   2년 전

감사합니다!!! bfs로 다시 해볼게요!

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