lyzqm   4년 전

문제를 잘못읽어서 다른 문제를 풀고있었네요...

"동전 배열의 양 끝에서 벗어나서 양 끝의 동전만 뒤집거나 양 끝의 두 개 동전만 뒤집는 것도 가능하다. 동전을 뒤집는 횟수에 제한은 없다."

궁금한게 생겼는데 위의 조건이 없다면 dp로 푸는게 타당할까요?

dp1[idx][a][b][c] : {arr[idx], arr[idx+1], arr[idx+2]}에서 {a,b,c}가 각각 0이면 그대로, 1이면 뒤집는 형식에서의 (최댓값)


vc0612   4년 전

어음ㅁ.. 저조건덕분에 그냥 다 절댓값 씌워서 더해주면 되는 쉬운문제가 되어버렸죠.... 

저 조건이 없다면 절댓값으로 쉽게 푸는게 안되요..!

그래서 저조건이 없다면 간단하게 안되고 어쩔 수 없이 dp로 풀어야해요 ㅠㅁㅠ...

그런데ㅔ... 양끝 두개 동전만?..은 잘모르겠지만 한개 동전만 불가능하게 할경우는 

각끝만 뒤집혀 있는 경우만 불가능하니깐 그거 고려해주면, 뭐 dp 없이 if문 두개만 추가해줘서 풀 수 있긴해요.


양끝 두개 동전뒤집기도 불가능하게 하면ㄴ...(생각하기 너무 귀찮은 상태.... 덥다...)

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