poirin   6년 전

DFS로 풀었는데 여러가지 안나오는 경우 고려해도 시간복잡도가 2^300은 나오는것 같습니다.

혹시 DP로 푸는건가요?

3587jjh   6년 전

1. 퍼즐을 푸는데 각각의 버튼들은 최대 한 번만 눌러봐도 됩니다 (두 번 누르면 안누른거랑 같으니까 의미없음)

2. 버튼들을 누르는 순서는 상관이 없습니다


2째행/ 3째행/ ...,/ N째행 같이 행단위로 버튼들을 적절히 눌러서 그 윗 행에 있는 모든 전구를 끈다고 합시다

초기상태는 맨 처음 시작상태에서 1째행의 버튼들의 특정 조합을 누른 후의 상태입니다 (총 2^N가지가 되겠죠)

EX)

1) 초기:

0 1 1 0 0

1 0 0 1 1

0 1 0 0 1

0 1 0 0 0

2) 2째행의 버튼들을 눌러서 1째행의 전구를 모두 끄기: 2째행의 2열,3열 버튼을 누르는 조합이 유일

0 0 0 0 0

0 0 0 0 1

0 0 1 0 1

0 1 0 0 0

3) 3째행의 버튼들을 눌러서 2째행의 전구를 모두 끄기: 3째행의 5열 버튼을 누르는 조합이 유일

0 0 0 0 0

0 0 0 0 0

0 0 1 1 0

0 1 0 0 1

4) 4째행의 버튼들을 눌러서 3째행의 전구를 모두 끄기: 4째행의 3,4열 버튼을 누르는 조합이 유일

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

5) 맨 마지막 행의 전구가 모두 0이므로 전구를 모두 끄는게 가능합니다


poirin   6년 전

감사합니다. 한번해보겠습니다!!!

poirin   6년 전

풀었습니다 감사합니다 ㅎㅎ

leehanjun   6년 전

질문이 있는데, 해당 방법이 최적값을 구한다는 것을 어떻게 보장할 수 있을까요??

rdd6584   5년 전

@leehanjun

일단 맨처음에 첫행에 대한 모든 경우의 수를 다 만들어 놓으면,

그 다음부터는 경우의 수가 한 가지 밖에 없기 때문이에요 !

leehanjun   5년 전

@rdd6584

감사합니다.!!

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