lyzqm   4년 전

방석의 최소 개수를 BFS로 구했습니다. 

http://contest.usaco.org/TESTD... << 여기서의 TC를 확인해 보면 최소개수는 맞는데

방석을 놓는 경우의 수가 약간씩 틀리네요.

16개의 TC중 8,10,13번빼곤 다 맞는데 뭐가 문젠지 모르겠습니다.

dp로 경우의 수를 구했는데 점화식은 

"dp[N][M][K] : (N,M)위치에 K개의 방석을 놓는 개수" 형태로 했습니다.


8번TC를 예를 들면

7 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 2 0 1 1 1 0 2 0 0 0 0
0 0 3 0 0 0 1 0 1 0 0 0 4 0 0
0 0 0 0 2 0 1 1 1 0 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

답 : 4 , 36

저는 4, 64가 나옵니다 ㅠㅠ

dp고수님들 어떤 논리식이 잘못됬는지 도와주세요


다시보니 "방석을 최소한으로 놓았을때 목표지점까지 가는 경우의 수"로 정의하고 풀었네요 ㅋ;

minjae200   3년 전

@lyzqm

저 잘이해가안가서 그러는데요

방석 3개를 최소한으로 놓고 목적지에 갈수있으면 방석3개만 놓고 가는 경우의수를 구하는거아닌가요?

minjae200   3년 전

@lyzqm

저도 4,64가 나와서 ㅠㅠ 질문드립니다

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