백준 이거 어케 풀지 감이 안옴

[익명(59.25)]

쉬운거 맞냐? 

[히웅(oskarchen)]

나 이거 풀었었는데 링크점

[익명(59.25)]

https://www.acmicpc.net/problem/13413

[익명(223.62)]

이거어렵던데

[익명(222.236)]

BFS, 개쉬운거

[익명(222.236)]

각 노드마다 두 경우의수를 탐색해가면서 BFS로 내려가고, 정답을 찾으면 loop 빠져나오고 스택 클리어

[레후쿤(121.186)]

일단 벡트래킹으로 접근한 다음에 dp로 최적하 하봐(이리 말하면 있어보임 ㅇㅅㅇ)

[익명(59.25)]

[레후쿤(121.186)]

위에덧글보니 dp좆도 피료없것다 ㅇㅅㅌ

[레후쿤(121.186)]

꼬멘..

[레후쿤(121.186)]

아니 그냥 규칙찾아서 푸는것도 가능할듯 ㅇㅅㅇ

[레후쿤(121.186)]

우선 목표상태와 흑백 개수기 같아질때까지 뒤집기 하고 나머지는 스와핑으로 해결한다 가정하면. 스와핑 시점에서 홀인지 짝일지에 따라도 달라질거 같은데

[레후쿤(121.186)]

아니다 홀짝은 상괸없구나.. 졸려서 몰겄다. 여튼 저거 규칙찾아서 풀수있는 문제임

[레후쿤(121.186)]

요는 처음에 주어진 값하고 목표값하고 w와 b의 개수의 차이 + 다른거 뒤집는 식으로 임의로 개수의 차이를 맞춘 상태의 배열과 목표값의 다른부분/2 인듯 ㅇㅅㅇ.. bfs니 dp니 피료없다봄 ㅇㅅㅇ... 아님말구