1600번 - 말이 되고픈 원숭이
DP로만 풀 수 있을까 고민해보다가 생각해본 점을 작성해봅니다.
코드는 DP로만 풀려다가 실패한 코드입니다.
DP로 풀려면 그 자리까지 가는 원숭이 동작수의 최소값을 업데이트를 해줘야 하는데
for문으로 어떠한 방향성을 가지고 업데이트를 해야 합니다.
하지만 가는 길이 분명하게 존재하는데 방향성이 꼭 우하단 쪽이 아닌 경우
다른 말로 말하면 아래로 갔다가 오른쪽으로 갔다가 위로 갔다가 왼쪽으로 갔다가 위로 갔다가 등 여러 방향으로 변경하며 가는 길로 이동해야 할 경우
DP배열을 for문으로 업데이트 할 때 얼마나 어떤 방향으로 값을 업데이트 해줘야 하는지 알 수 없습니다.
테스트케이스 예시
310 40 1 0 0 1 1 1 1 1 10 1 0 1 1 0 1 1 1 10 0 0 1 1 1 1 0 1 11 1 1 1 1 1 1 1 1 0답 : 1017 50 1 0 0 0 0 00 1 0 1 1 1 00 1 0 1 0 0 00 0 0 1 1 1 11 1 1 1 1 0 0답 : 1614 40 1 1 10 0 1 11 0 1 11 1 1 0답 : 455 80 0 0 0 01 1 1 1 01 1 1 1 00 0 1 1 00 1 1 0 00 1 1 1 10 1 1 1 10 0 0 0 0답 : 1156 80 0 0 0 0 01 1 1 1 1 01 1 1 1 1 00 0 0 1 1 00 1 1 1 0 00 1 1 1 1 10 1 1 1 1 10 0 0 0 0 0답: 1457 80 0 0 0 0 0 01 1 1 1 1 1 01 1 1 1 1 1 00 0 0 1 1 1 00 1 1 1 0 0 00 1 1 1 1 1 10 1 1 1 1 1 10 0 0 0 0 0 0답: 1757 80 0 0 0 0 0 01 1 1 1 1 1 01 1 1 1 1 1 00 0 0 1 1 1 00 1 1 1 0 0 00 1 0 1 1 1 10 1 1 1 1 1 10 0 0 0 0 0 0답: 1358 80 0 0 0 0 0 0 01 1 1 1 1 1 1 01 1 1 1 1 1 1 00 0 0 0 1 1 1 00 1 1 1 1 0 0 00 1 1 1 1 1 1 10 1 1 1 1 1 1 10 0 0 0 0 0 0 0답: 2022 60 11 11 01 10 10 0답 : 4210 20 0 1 0 0 1 0 0 1 00 0 1 1 0 0 0 0 1 0답 : 1029 20 0 1 1 0 0 1 1 00 0 1 0 0 0 1 0 0답 : 715 30 1 0 0 00 1 0 1 00 0 0 1 0답 : 611 10답 : 0210 20 0 1 0 0 1 0 0 1 00 0 1 1 0 0 0 0 1 0답 : 1015 50 1 1 0 10 0 1 0 10 1 0 1 10 1 0 1 01 1 0 1 0답 : -125 30 0 0 0 01 0 1 1 01 0 1 1 0답 : 456 60 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답 : 414 40 0 0 00 0 0 00 0 1 10 0 1 0답 : 4
댓글을 작성하려면 로그인해야 합니다.
mychoi1199 2년 전 6
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