kskung2   6달 전

비트마스크로 상태공간 만들어서 해결하려고 했는데 어느 부분에서 틀렸는지 감이 잘 오지않습니다.ㅠㅠ

구현방식이 잘못되었나요?

dp 구현을 잘못하신것같습니다.

현재는 dp[현재 키는 인덱스][상태] ? 이렇게 하신것 같은데

dp[상태] 를 이용해서 1차원dp 해결할 수 있습니다.

상태 하나만으로 어떤 발전소들이 켜져있는지 알 수 있고, 켜져있는 발전소의 숫자도 알 수 있기 때문이죠

그리고 if (state[i - 1] == 'Y') // 켜져 있을 때

로 처리를 하고계신데, 이건 최초 발전소의 상태에 대한 정보만 가지고있기 때문에 해당 조건문을 가지고는 현재 상태에서 발전소가 켜져있는지 아닌지 판단할 수 없습니다.

if (cur & (1 << (i - 1)) 로 하셔야 겠지요.

kskung2   6달 전

저기 켜져 있을 때 처리한 부분도 최초상태에서 켜야하는 발전소들에 대해서만 가중치를 더한다는 생각으로 켜야하는 발전소들만

해당 상태의 켜져있는 발전소들 중에서 가중치를 더하는식으로 구현을 했는데 켠 순서가 상관이 없으니 1차원으로 해결이 가능하겠네요. 

1차원으로 수정하고도 아직 정답이...

그럼 아래 소스처럼 어떤 상태에 대해 꺼져있는 발전소를 켤 수 있는 경우를 생각해서 최소값을 갱신해나가는 식으로 구현을 했는데

처리가 조금 미흡한지 정답이 아니네요ㅠ 이런유형 처음풀어보는거라 아직 익숙치가 않아서..

혹시 이 방법도 잘못된 부분이 있나요

문제가 다른곳에 있었네요 ^^;

발전소를 가동하는데 필요한 비용이 0인 경우도 있네요.

if (cost[j][k] 조건을 없애주시면 정답이 나옵니다.

가장 처음 올려주신 소스코드도 해당 조건을 제거하면 정답이 나오네요!

그리고 두번째 소스에서 

if (cost[j][k] && !(i & 1 << (k - 1))) // j 가 k 를 켤 수 있다

에 & 연산 뒤에 괄호가 하나 빠져있어요

그것도 고쳐주시면 정답으로 나오네요 !!

kskung2   6달 전

비트연산할 때 괄호가 상당히 중요하네요 .. ㅎㅎ

첫번 째 말씀하신 것도 문제 조건에 비용이 자연수라고 되어있어서 0을 포함시키지 않았는데 . . 이상하군요 ㅋㅋㅋ

미흡한점 많이봐주셔서 감사합니다 ~~ 덕분에 잘 해결되었어요!

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