adh0463   2년 전

안녕하세요

이동하기 2문제를 풀고있는데요..

(1,1)에서 (N,N)으로 K번 간다고 하니까 이건 while(k--)로 돌렸고, 나머지 부분은 dynamic으로 구성햇어요

(1,1)부터 (N,N)까지 다이나믹으로 돌면서 어디서 왔는지를 저장하는 previous 배열 변수를 사용해서 (N,N)에서 시작해서 (1,1)까지 결정된 경로가 하나니까 마치 최대 유량문제 풀듯이 했어요.. 각 previous 배열 변수 하나는 (i,j)을 저장할 수 잇고 이는 행 i, 열 j에서 온 것을 말해요. 그 경로를 따라가면서 사탕 갯수를 저장하는 2차원 배열 A라고 할때, A[i][j] = 0으로 처리해 주는거죠, 이미 먹었으니.

한 번 루프를 돌면 A[1][1] = A[N-1][N-1]= 0; 을 처리하도록 했어요, 어차피 (1,1)에서 (N,N)으로 가는거니까 두 위치에 있는 사탕은 먹을 수 밖에 없다고 생각햇어요

마치 K 루프를 돌 때마다 "BOJ 11048 - 이동하기"를 계속 수행하는건데, 제 접근 방식이 잘못 된건가요 ??

jh05013   2년 전

다이나믹 K번으로는 이런 반례가 존재합니다. 이동하기 1과 풀이법이 매우 다른 문제입니다.

다이나믹 두 번: 1->4->5->8->1, 0->0->7->3->0, 총합 29

정답: 1->2->6->8->1, 0->4->7->3->0, 총합 32

adh0463   2년 전

아.. 그렇군요..

다른 방식으로 접근해봐야겠어요, 감사합니다 ㅎㅎ!

adh0463   2년 전

(to cheetose) 아 역시..ㅋㅋㅋㅋ 그래프 모델링이엿꾼요!!! 휴..ㅋㅋㅋ 힌트 감사합니다

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