mychoi1199   2년 전

DP로만 풀 수 있을까 고민해보다가 생각해본 점을 작성해봅니다.

코드는 DP로만 풀려다가 실패한 코드입니다.

DP로 풀려면 그 자리까지 가는 원숭이 동작수의 최소값을 업데이트를 해줘야 하는데

for문으로 어떠한 방향성을 가지고 업데이트를 해야 합니다.

하지만 가는 길이 분명하게 존재하는데 방향성이 꼭 우하단 쪽이 아닌 경우

다른 말로 말하면 아래로 갔다가 오른쪽으로 갔다가 위로 갔다가 왼쪽으로 갔다가 위로 갔다가 등 여러 방향으로 변경하며 가는 길로 이동해야 할 경우

DP배열을 for문으로 업데이트 할 때 얼마나 어떤 방향으로 값을 업데이트 해줘야 하는지 알 수 없습니다.


테스트케이스 예시

3
10 4
0 1 0 0 1 1 1 1 1 1
0 1 0 1 1 0 1 1 1 1
0 0 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 0

답 : 10

1
7 5
0 1 0 0 0 0 0
0 1 0 1 1 1 0
0 1 0 1 0 0 0
0 0 0 1 1 1 1
1 1 1 1 1 0 0

답 : 16

1
4 4
0 1 1 1
0 0 1 1
1 0 1 1
1 1 1 0

답 : 4


5
5 8
0 0 0 0 0
1 1 1 1 0
1 1 1 1 0
0 0 1 1 0
0 1 1 0 0
0 1 1 1 1
0 1 1 1 1
0 0 0 0 0

답 : 11


5
6 8
0 0 0 0 0 0
1 1 1 1 1 0
1 1 1 1 1 0
0 0 0 1 1 0
0 1 1 1 0 0
0 1 1 1 1 1
0 1 1 1 1 1
0 0 0 0 0 0

답: 14


5
7 8
0 0 0 0 0 0 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 0 0 1 1 1 0
0 1 1 1 0 0 0
0 1 1 1 1 1 1
0 1 1 1 1 1 1
0 0 0 0 0 0 0

답: 17


5
7 8
0 0 0 0 0 0 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 0 0 1 1 1 0
0 1 1 1 0 0 0
0 1 0 1 1 1 1
0 1 1 1 1 1 1
0 0 0 0 0 0 0

답: 13


5
8 8
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 1 1 1 0
0 1 1 1 1 0 0 0
0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0

답: 20


2
2 6
0 1
1 1
1 0
1 1
0 1
0 0

답 : 4


2
10 2
0 0 1 0 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1 0

답 : 10


2
9 2
0 0 1 1 0 0 1 1 0
0 0 1 0 0 0 1 0 0

답 : 7


1
5 3
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0

답 : 6


1
1 1
0

답 : 0


2
10 2
0 0 1 0 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1 0

답 : 10


1
5 5
0 1 1 0 1
0 0 1 0 1
0 1 0 1 1
0 1 0 1 0
1 1 0 1 0

답 : -1


2
5 3
0 0 0 0 0
1 0 1 1 0
1 0 1 1 0

답 : 4


5
6 6
0 0 0 0 0 1
0 0 0 1 0 1
0 1 0 0 0 1
0 1 0 0 1 0
0 0 0 0 0 1
1 0 0 0 1 0

답 : 4


1
4 4
0 0 0 0
0 0 0 0
0 0 1 1
0 0 1 0

답 : 4

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