14939번: 불 끄기
전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄
www.acmicpc.net
비트마스킹과 브루트포스를 이용한 문제이다.
가로의 길이가 10밖에 안되므로 조합을 구성하면 2^10 이고 전부 도는거 10*10 으로 해서
시간복잡도 계산을 하였다.
또한 비트마스크를 이용한 조합구현 코드를 이용해서 구현하였다.
for (int subset = set;; subset = ((subset - 1) & set))subset이 0인것도 확인을 해야하므로 for문 안쪽에서 subset = 0이면 탈출조건을 넣었다.
비트에 관한 내용은 추후에 블로그에 써놓을 예정이다.
첫번째 줄을 돌면서 subset에 따라 버튼을 클릭했다면 그 이후엔 아래쪽을 선택해야한다.
두번째 줄부터는 바로 위칸을 보면서 위칸이 켜져있다면 해당 버튼을 클릭해야한다.
왜? 위쪽이 켜져있으면 바로 아래칸을 누르면 위쪽을 끌 수 있기 때문이다.
왜 켜져있는 오른쪽 왼쪽을 클릭하면 안되나요?
그리디한 접근 방식이기 때문에 오른쪽 왼쪽 보단 바로 아래칸을 클릭하면 해당칸이 꺼지기 때문입니다.
또한 맨 윗줄을 이미 지정을 해놨기 때문에 모든 경우의 수를 볼 수 있습니다.
이제 해당칸의 윗칸이 켜져있다면 해당칸을 클릭하는 방식으로 배열을 돌아줍니다.
작업종료후 모든 배열을 돌면서 켜져있는 전구가 있는지 확인을 하면 됩니다.
코드
'Algorithm' 카테고리의 다른 글
| 프로그래머스 - 카드 짝 맞추기 / C++ (2) | 2021.03.24 |
|---|---|
| 백준 - 14442번(벽 부수고 이동하기 2) / C++ (4) | 2021.03.16 |
| 백준 - 17831번(머기업 승범이네) / C++ (0) | 2021.03.10 |
| 프로그래머스 - 매출 하락 최소화 / C++ (2) | 2021.03.08 |
| 프로그래머스 - 합승 택시 요금 / C++ (0) | 2021.03.05 |