1285번: 동전 뒤집기
첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위
www.acmicpc.net
그리디, 브루트포스, 비트마스킹을 이용한다.
처음에 문제를 잘못읽었는데 동전을 선택하는 것이 아니라 행이나 열을 선택하는 것이었다.
문제를 제대로 읽고나니 풀이방법이 바로 떠올랐다.
풀이 방법:
비트마스킹을 활용하여 20개의 조합(100만 정도임)을 전부 해볼 것인데,
만약 행과 열 모두 브루트포스로 돌리게되면 (100만*100만)으로 시간초과가 난다.
그래서, 열만 조합을 돌려 뒤집어주고,
행은 뒷면인 동전의 개수만 세서 만약 앞면인 동전의 개수보다 많다면 뒤집는 방식으로 하였다.
시간초는 6초가 주어지지만 1초내로 풀린다.
코드:
'Algorithm' 카테고리의 다른 글
| 백준 - 21611번(마법사 상어와 블리자드) / C++ (0) | 2021.05.11 |
|---|---|
| 백준 - 8111번(0과 1) / C++ (4) | 2021.04.05 |
| 프로그래머스 - 카드 짝 맞추기 / C++ (2) | 2021.03.24 |
| 백준 - 14442번(벽 부수고 이동하기 2) / C++ (4) | 2021.03.16 |
| 백준 - 14939번(불 끄기) / C++ (0) | 2021.03.12 |