https://school.programmers.co.kr/learn/courses/30/lessons/60059
내가한건
열쇠돌린것들을 keys에 저장해서 keys에 4개의 열쇠를 만들고
lk를 key의 한 변의 길이라하면
lock을 lk-1 4방향 제로패딩하고 (이것을 pad라고하자)
pad에서2중반복문돌려가며
각 좌표에서 key가 lock의 0을 다 1로 만들수 있나,lock의1인부분과 key의 1인부분이 겹치지않는가 를 체크함
체크하는 방법은 각 2차원배열의 원소를 비교
만약 lock의 0을 다 지울 수 있는 경우가있음 참 리턴
이러면 복잡도가 4(열쇠의개수)*lock의길이^2*key의길이^2가되는데
더 효율적인 풀이 없을까
논리식 1차원으로 풀어서 논리연산 조지려했는데 대가리 터질거같아서 포기함
내가한건
열쇠돌린것들을 keys에 저장해서 keys에 4개의 열쇠를 만들고
lk를 key의 한 변의 길이라하면
lock을 lk-1 4방향 제로패딩하고 (이것을 pad라고하자)
pad에서2중반복문돌려가며
각 좌표에서 key가 lock의 0을 다 1로 만들수 있나,lock의1인부분과 key의 1인부분이 겹치지않는가 를 체크함
체크하는 방법은 각 2차원배열의 원소를 비교
만약 lock의 0을 다 지울 수 있는 경우가있음 참 리턴
이러면 복잡도가 4(열쇠의개수)*lock의길이^2*key의길이^2가되는데
더 효율적인 풀이 없을까
논리식 1차원으로 풀어서 논리연산 조지려했는데 대가리 터질거같아서 포기함
브루트포스아니면 답 없는거 맞는거같은데
ㅇㅋ 만족해야지
2²⁰인 수로 나타내서 비트마스킹하는 식으로 최적화할 수야 있겠지만 그래봐야 겨우 M²(<=400)깎는거같고,,
음 사실 인풋제한이 다 작아서.. 의도자체는 구현하고 브루트포스로 푸세요~가맞는거같은데 찝찝하네