그리디 썸네일형 리스트형 백준 14939 불 끄기 비트마스킹 분류로 되어있는 문제이다. 처음 접근할때, 모든 스위치 상황을 비트마스킹으로 만들까 했는데, 10*10 맵을 비트마스킹으로 표시하면 이걸 담을 자료형이 마땅치 않아 접었다. 물론 여러개의 변수를 사용해서 만들 수는 있지만, 그렇게까지 해야할까... 싶었다. 문제가 속한 다른 분류에 그리디가 있어서 한번 생각을 꼬아봤다. 맨 윗줄만 탐색하고 나머지는 그때 그때 상황에따라 계산해보자... 첫 줄에 불을 켜냐 끄냐 경우의 수는 2^10이다. 따라서 그 경우의 수 만큼 탐색을 한다. 첫 줄의 상황에 맞게 스위치를 눌러놓고, 다음 줄 부터 마지막 줄 까지는 윗 줄 같은 열이 켜져있을 때 스위치를 누르는 선택을 한다. 이 때, toggle() 함수를 따로 만들어, temp[][]배열에 변경사항을 실행해준.. 더보기 이전 1 다음