격자를 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을 채워나가시면, 세우신 점화식에 대한 반례가 있다는걸 찾을 수 있을거같아요.

lsc4719  

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

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

...

이러면 반례인거같아요

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를 채워나갈 때,

↙

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

↙↙

↙

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

↙↙↙

↙↙

↙

...

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

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

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