728x90 백준브실골/Bitmasking2 백준 25047, 사각형 게임 (Large) 개요 문제 링크 골드 3, Bitmasking, 게임이론 N×N 크기의 행렬을 행->열 순으로 색칠할 때 한 번 색칠된 지점의 합의 최댓값 구하기 접근 비트마스킹 & 게임이론이라니, 천재의 영역 두 개가 모였다. 우선 XOR을 만족할 때 합의 최댓값을 구하는 것인데, XOR은 전혀 사용하지 않는다. 차라리 게임이론의 내용이 핵심인데, 민우가 먼저 선택을 하고 그 다음 종진이가 선택한다. 이때 종진이는 항상 최적의 선택을 하므로, 민우의 어떤 선택에도 자신의 점수를 최대로 만들어야 한다. 따라서 우리는 민우의 모든 선택에 대해서 종진이가 만들 수 있는 점수의 최댓값을 구한다. 그리고 전체 합에서 종진 점수를 뺀 값의 최댓값이 민우가 얻을 수 있는 최대 점수이다. 핵심은 민우가 아닌 종진이인 것이다. 민우의.. 2023. 2. 22. 백준 5831, Blink 개요 문제 링크 골드 3, Bitmasking 왼쪽 비트가 켜져있는 경우 toggle하는 과정을 B번 진행하기 접근 비트마스킹 문제는 즐겨 푸는 편은 아니지만 컴퓨터의 근본이라 풀때마다 재밌다. 코드포스 D나 E에는 거의 항상 비트마스킹이 나오는 것 같아서 틈틈이 공부해야겠다. 비트마스킹의 핵심은 XOR이다. 대부분의 문제는 XOR만 다루는데 왜일까? 공학적으로 유용하기 때문인 것 같다. XOR의 원리는 toggle인데, 비트 덧셈의 근본이 toggle이기도 하고, 스위치의 역할을 하기 때문에 논리회로에도 많이 사용된다. 트랜지스터도 디지털 상에서는 XOR과 크게 다를 것이 없다. Threshold를 넘으면 전류를 흘려보내기 때문. 나머지는 자세히 기억나지 않는다.. 이 문제는 어떻게 푸느냐? 우선 to.. 2023. 2. 17. 다음 728x90