koka   10달 전

완탐으로 해도 최대 경우의 수가 8개일 수 밖에 없을 것 같아서 아래와 같이 풀었습니다..
80프로 대에서 계속 틀리는 데, 이유를 못찾겠어요.. 고수님들 도와주세요..

js7777   10달 전

input

3 4

output

7

answer

8


set으로 관리하면서 dfs를 돌리면 더 최적인 방법을 발견하지 못할수도 있습니다.

입력이 3 4 인 경우

000 동작x, 0초

001 동작3+동작4, 2초

010 동작2, 1초

011 동작2+동작3+동작4, 3초

100 동작4, 1초

101 동작3, 1초

110 동작2+동작4, 2초

111 동작1, 3초

이렇게 모든 경우를 다 만들 수 있어서 답은 8입니다. (버튼이 눌린 상태면1, 꺼진 상태면 0)

하지만 dfs는 동작1, 동작2, 동작3, 동작4 순서로 돌기 때문에

101을 만들때, 동작1+동작2인 상태를 먼저 방문합니다.

그럼 이후에 동작3을 통해서 101을 만들어도, 이미 set에 포함되어있어서 바로 return당하고, 결과적으로 001을 만들 수 없다고 판단합니다.

(만약 101을 동작3을 통해서 1초만에 만들었다면, 거기서 동작4를 수행하여 총 2초의 시간으로 001을 만들 수 있습니다.)

그래서 set에 넣고 이후 중복이면 바로 return하는게 아니라, 최적인 경우에는 갱신을 해주어야합니다.

js7777   10달 전

바로 다음 질문글에서 유용한 질문을 해서 답변했는데, 질문글을 삭제하셔서 추가로 여기다 남깁니다.


질문자님의 코드에서 dfs를 할때 재귀 진입 순서를 동작4, 동작2, 동작3, 동작1 순서로 해주면 갱신 없이도 정답을 맞출 수 있습니다.

이 문제에서 동작 순서는 상관이 없습니다. 같은 동작을 두번 이상 수행할 필요가 없고, 동작에서 하는건 버튼의 상태를 바꾸는것밖에 없기 때문이죠.

각 동작의 비용을 계산해보면, 동작4는 N/ 3, 동작2는 N/2, 동작3은 N/2, 동작1은 N정도의 시간이 드는것을 알 수 있습니다.

앞서 말했듯이 동작 순서는 상관이 없기 때문에, 같은 상태를 만들 수 있으면 더 적은 시간을 들이는것이 이득입니다.

그래서 dfs로 재귀를 할때에도, 더 적은 시간을 들이는 동작부터 먼저 방문함으로써 문제를 해결할 수 있습니다.

koka   10달 전

고수님 덕분에 문제 해결을 했는데 답글을 못남겨드렸네요!
적어주신 내용을 보고 아차했습니다..

정말 오랜만에 알고리즘 공부를 다시 시작했는데 앞으로 다시 열심히 정진해봐야겠군요..

친절한 답변 남겨주셔서 감사합니다!

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