인프런 커뮤니티 질문&답변
작성한 질문수
4-B 질문있습니다.
해결된 질문
작성
·
216
0
이 문제를 보고 큐브 같다는 생각이 들었습니다. 행을 뒤집을 수도, 열을 뒤집을 수도 있으니 결론적으로 0행과 0열을 뒤집으면 0행0열의 원소는 그대로지만 나머지 0행과 0열의 원소는 뒤집은 결과를 갖게 되니까요.
111
111
111 이
100
011
011
처럼 된다는 말입니다.
근데 저는 이 문제를 보고 도저히 행 또는 열을 선택해서 완전탐색을 하면 정답을 구할 수 있다. 는 사실을 혼자서 생각하지 못했습니다. 이유는 아까 예시와 같이 행과 열을 순차적으로 조작하면 개별요소도 수정할 수 있지 않을까? 하는 생각이 들어서 였습니다. 과연 코테에서 이런 아이디어를 떠올릴 수 있을지.. 자신이 없습니다.. 혹시 이 아이디어를 어떻게 생각하셨는지 궁금합니다.
감사합니다.
답변 1
1
안녕하세요 ㅎㅎ
이런 플로우를 통해서 생각했습니다.
1.처음에는 완탐. -> 시간복잡도가 너무나도 큰 것을 알 수 있습니다.
2.그렇다면 DP일까? 상태값 담기가 힘든데..
3.그리디일까? 경우의 수 다 체크해봐야 할 것같은데. (그리디는 굉장히 틀리기 쉬운 알고리즘입니다. 주의해서 사용해주셔야 합니다.)
완탐에서 경우의 수를 줄일 수 있는 방법이 없을까? 고정된 상수로 쓸만한 것은?
열을 다 뒤집었을 때 행 뒤집는 것은 최적해가 있구나.
이부분은 고정된 상수로 써보자. (뒤집 또는 안뒤집)
시간복잡도 해결 -> 제출
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.