[일반] 파댕이 d는 bfs인가요?

[이세계정서(shutupandcalculate)]

말이 되고픈 원숭이 문제처럼

p+1의 무리를 데려가기, 그냥 지나가기

p-1의 무리를 데려가기, 그냥 지나가기

이런식으로 케이스를 나눠서 2차원으로 확장하고 잘 움직이는 문제인가 싶은데...

셤 기간만 아니면 계속 붙잡고 풀고싶은데 시간이 없네여

아이디어만 맞는지 확인해보고싶어요

[익명(58.79)]

냅색이래요

[이세계정서(shutupandcalculate)]

[익명(180.70)]

맨처음 파댕이가 있는 위치를 기준으로, 좌측 영역과 우측 영역을 따로따로 생각해봐 그러면 이동할 수 있는 시간에 따라서 최대로 방문 가능한 영역이 나올거임 이 영역은 여러 가지 경우가 생길 수 있는데, 하나의 경우가 고정되었다고 생각하면 왼쪽 영역으로 a칸, 오른쪽 영역으로 b칸 이동할 수 있게 됨. 이 영역에 있는 모든 무리들은 점령하고 안 하고가 자유이니 (a+b)개의 영역을 냅색으로 하면 그 경우에 대해 정확히 M만큼의 무리를 형성할 수 있을지가 정해짐

[익명(180.70)]

문제는 이제 조건을 만족하는 (a, b)가 여러 개 있을 수 있다는 건데 a 값을 0, 1, 2, ..., 로 정했을 때 b 값의 최댓값을 각각 찾아서 딱 한 번씩만 냅색을 돌려보면 됨

[이세계정서(shutupandcalculate)]

셤 끝나면 다시 도전해보겠습니다.. 감사합니다!