sweet   2년 전

우선 저는 bottom-up approach로 풀었습니다. (재귀사용 x)

이 문제를 풀 때, 핵심은 중복 연산을 어떻게 피하는가? 를 고민해보면 답을 찾는데 도움이 됩니다. (이 정도는 생각한 분들이 많을 거라 봅니다.)

하지만 문제는 '답이 없을 때' 혹은 경우의 수가 많이 존재할 때, 입니다. 

처음엔 단순히 답을 찾고 답의 위치에서 부모를 역추적 해나가는 식으로 해서 최적화 하였습니다. (물론 dp로 풀었습니다.) 하지만 시간초과가 뜨더군요..

제가 놓친 점은 바로, 답이 아닌 경로를 최적화 하지 않았다는 점에 있습니다. 이 문제를 풀 때, 답이 아닌 경로도 dp로 최적화 해줘야 풀립니다.

답이 아닌 경로에 대한 최적화 방법은 2차원 배열의 각 요소에 -1로 만들어 주고, 최초로 지나친 위치는 0으로 만들어줘 0이라면 접근을 막아주게 구현을 해주면 됩니다.

추가로 아래 code를 넣어보면 1초만에 답이 나와야 하는데, 답이 안나오는 경우라면 시간초과가 뜰 것이라 생각하면 됩니다.

==========================================

18 18
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19
35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18
34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17
33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16
32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 10000

답 0

===========================================

4 5

50 45 37 32 30

35 50 40 20 25

30 30 25 17 28

27 24 22 15 10

답 3

///

///

4 4

93 72 61 58

90 73 19 49

85 36 75 13

21 41 45 7

답 2

///

///

7 7

100 33 58 59 61 31 30

74 31 55 62 70 70 29

73 98 49 47 11 10 36

62 59 56 45 44 8 7

59 58 54 53 41 7 3

56 32 29 18 40 4 3

34 31 26 40 39 73 1

답 27

///

///

5 5

27 26 25 24 23

28 29 30 31 22

17 18 19 20 21

16 32 33 34 35

15 14 13 12 11

답1

///

///

1 1

1

답1

///

///

4 5

50 45 37 32 30

35 50 40 20 25

30 30 25 17 28

27 24 22 15 10

답 3

///

///

2 18

98 91 89 80 76 74 65 58 50 49 44 32 26 23 17 15 14 8

95 91 83 82 70 67 65 55 54 50 41 27 22 20 14 10 7 3

답 211

///

///

1 2

1 1

답 0

///

///

2 2

1 2

2 1

답 0

///

///

2 3

5 4 1

4 3 2

답2

///

///

4 4

16 9 8 1

15 10 7 2

14 11 6 3

13 12 5 4

답 10

///

///

3 3

9 4 3

8 5 2

7 6 1

답6

///

///

3 5

55 99 49 48 47

54 99 50 99 46

53 52 51 99 45

답1

///

///

4 4

9 8 7 6

8 7 6 5

7 6 5 4

6 5 4 3

답20

전부 통과하였는데, 더 없을까요?

siyamaki   2년 전

경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다

라고 문제에 제시되어 있으니 INFINITY 값을 20억정도로 하시면 될 것 같습니다

sweet   2년 전

Aㅏ.. 문제를 풀었습니다. 답변 감사합니다.

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