wooljs   2년 전

테스트 케이스 만들어 본 것들에 대해서는 전부 통과합니다.

섭밋을 해보면 제출하자마자 틀렸다고 나오는데,

어느 부분에서 잘못했는지 잘 모르겠습니다. 

bfs + dp 스럽게 짰습니다. 


(소스는 뒤에 분들을 위해 지웠습니다. )

lsc4719   2년 전

격자를 A라고 이름붙이면요,

A(i, j)를 격자 A의 i번째 행, j번째 열에 위치한 칸의 값이라고 정의하면요~

격자 A에 대응하는 DP 표인 visited(i, j)를 만드셨잖아요?

visited(i, j)를 채워나가실 때,

visited(1, 1)을 제일 먼저 채우고 (1<=i<=격자 A의 높이, 1<=j<=격자 A의 너비),

그 다음엔 visited(1, 2), visited(2, 1)를 채우고...

이런식으로,

격자 visited의 / 방향 칸들을 채워나가야 하지 않을까요?

음.. 점화식을 세우신 걸 알려주시면

저런식으로 DP table을 채워나가시면, 세우신 점화식에 대한 반례가 있다는걸 찾을 수 있을거같아요.

wooljs   2년 전

lsc4719  

우선 댓글 달아주셔서 정말 감사합니다!

1. Visited[i][j] 정의
- i번째행, j번째열을 방문할 수 있는 최소 경로의 수 ( zero-based index)

2. 점화식
w = A[i][j]  ( A는 말씀하신 격자 )
Visited[i + w][j] = Visited[i + w][j] + Visited[i][j]  if (i+w, j) exists
Visited[i][j+w] = Visited[i][j+w] + Visited[i][j] if (i, j+w) exists

3. 채우는 방법
- BFS를 돌면서
   1. start는 (0, 0)
   2. 현재 노드의 이웃 노드 중에 방문하지 않은 노드가 있다면 (  if (i+w, j) or (i, j+w) exists, )
       방문하면서 위 점화식대로 한 번 더해주고, 현재 노드를 Queue에 push합니다.
   3. 만약 이웃 노드가 이미 방문한 노드라면 현재 노드의 위 점화식대로 한 번 더해주고, Queue에는 push하지 않습니다.
   4. Queue가 비면 종료합니다.

4. 답의 위치
Visited[N-1][N-1]
 
제가 DFS하고 섞어서 DP를 해본 경험이 없어서 어떻게 description을 써야할지 잘 모르겠습니다. -_ㅠ 

lsc4719   2년 전

음.. 3번에서 bfs로 돌아도 저 점화식대로 계산이 되는지 모르겠어요. 다순하게 / 요 방향 대각선을 옮겨가면서 대각선 위에 겹치는 칸들을 채우는 방법도 있을거같아여.  

lsc4719   2년 전

칸을 채우는게 아니라 써먹는 거요~ 음 반례는

lsc4719   2년 전

1 1 1 1 1 1 1 1 1

1 1 1 5 1 1 1 1 1

1 1 1 1 1 1 1 1 1

...

이러면 반례인거같아요

wooljs   2년 전

lsc4719

와... 답변 정말 감사합니다.

정말 말씀하신대로 bfs의 queue의 순서가 문제가 되네요.

[1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 1, 2, 3, 4, 9]
[1, 3, 6, 6, 7, 9, 12, 16, 20]
[1, 4, 10, 16, 23, 32, 44, 60, 64]
[1, 5, 15, 31, 54, 86, 130, 190, 194]
[1, 6, 21, 52, 106, 192, 322, 512, 516]
[1, 7, 28, 84, 110, 196, 326, 516, 8]
[1, 8, 36, 40, 8, 12, 16, 20, 28]
[1, 9, 45, 49, 12, 24, 40, 60, 88]

`다순하게 / 요 방향 대각선을 옮겨가면서 대각선 위에 겹치는 칸들을 채우는 방법도 있을거같아여.` 라고 말씀하셨는데,

DP를 채워나갈 때,

-------------

↙↙

--------------

↙↙↙

↙↙

...

와 같은 순서로 채워나가라는 말씀이신가요?

lsc4719   2년 전

음... 넵! 저는 그렇게 생각했어요~

Visited[i][j] = 0 for 0<=i<n, 0<=j<n

------

(i, j) = (0, 0)

Visited[i + w][j] = Visited[i + w][j] + Visited[i][j]  if (i+w, j) exists
Visited[i][j+w] = Visited[i][j+w] + Visited[i][j] if (i, j+w) exists

------

↙↙

(i, j) = (0, 1), (1, 0)

Visited[i + w][j] = Visited[i + w][j] + Visited[i][j]  if (i+w, j) exists
Visited[i][j+w] = Visited[i][j+w] + Visited[i][j] if (i, j+w) exists

------

...



lsc4719   2년 전

어, -> 요 방향 대각선으로 채우는 게 더 단순한거 같아여~

lsc4719   2년 전

-> 이건 대각선이 아니라 그냥 선이네요 -_-

wooljs   2년 전

lsc4719


맞았습니다. 띄웠네요. 감사합니다.

DP로 푸니까 무난하게 풀리네요.

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