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하는게 아니라, 최적인 경우에는 갱신을 해주어야합니다.

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