접근팀원 구성 점수 아래 요소들의 합계이다.(X, Y), (Y, Z), (X, Z) 의 천간 관계 점수, 지지 관계 점수X, Y, Z의 실력 값의 합계그렇다면 결국 메모는 필요한데 배열과 dict를 고민하던 중 조합을 사용해야 하는데 N이 10^6까지 가능하므로 비트마스킹을 쓰기에는 너무 크다고 판단하여 dict를 사용하기로 했다. dict를 사용해서 2가지 조합을 미리 만들고 여기서 한 명을 더 추가하는 식으로 하려고 했었는데 이를 구현하지 못했다. 결국 시간이 꽤 흘렀고 알고리즘을 확인해보니 비둘기집 원리 문제였다. 풀이비슷한 유형을 풀어보고 싶다면 이 문제를 풀어보자. 비둘기집 원리란 비둘기 집이 N개있고, N 보다 큰 M 마리의 비둘기가 있다고 가정하자. 이 때 최소 한 마리 이상의 비둘기는 다른..
implementation
풀이아래에서 다루는 CCTV 설치 예시는 (0, 0)을 기준으로 했다. 1번 CCTV초기 → (0, 1) 만 감시가능이후 최대 3번 회전 가능 → (1, 0), (0, -1), (-1, 0) 감시 가능 2번 CCTV초기 → (0, -1), (0, 1) 감시 가능최대 1번 회전 가능 → (-1, 0), (1, 0)3번 CCTV초기 → (-1, 0), (0, 1) 감시 가능최대 3번 회전 가능 → [(1, 0), (0, 1)], [(1, 0), (0, -1)], [(-1, 0), (0, -1)]4번 CCTV초기 → (-1, 0), (0, -1), (0, 1) 감시 가능최대 3번 회전 가능 → [(-1, 0), (0, 1), (1, 0)], [(0, -1), (0, 1), (1, 0)], [(-1, 0), (..
건물에 완전히 전파되기까지 시간이 걸려서 굉장히 까다로운 문제였다.건물이 완전히 전파되기까지는 방문처리를 하면 안되고, 완전히 전파되면 인접 구역으로 전파된다는 점이 고민을 많이 하게했던 문제같다.풀이 고민처음에는 큐에 (전파까지 남은 시간, y좌표, x좌표)의 형태로 관리하려고 했다. 만약 건물이라면 Tb의 시간을 넣고 이후 큐에서 빼고 1씩 감소시킨 뒤 다시 넣어줬고, 건물이 아니라면 0의 시간을 넣었다. 그래서 남은 시간이 0인 경우에만 인접 좌표로 전파시키도록 했는데, 아마 넣었다 빼는 과정에서 시간 초과가 난 것 같다. 그 뒤에는 방문 처리를 3차원 배열을 통해서 수행해보려고 했다. 건물이 Tb의 시간 이후에는 모든 층에 퍼지게 되므로 Tb의 층을 가진다고 볼 수 있다.이렇게 v[Tb][y좌표]..
1938 : 통나무 옮기기 처음에 계속 메모리 초과가 났는데 다시 생각해보면 회전 로직에서 시간 초과가 났던 것 같다.회전 시 통나무의 중심축을 제외한 두 좌표에 대해 y값과 x값이 바뀐다고 생각을 했었다.. 그렇게 생각하니 아래와 같이 정렬을 해줘야 했고 불필요한 리스트를와 패킹하기 위해 또다른 리스트를 만들었다. 아마 이부분에서 시간 초과가 난게 아닌가 싶다.# 따로 정렬이 필요if can_turn(y2, x2): # 변형 n_pos = sorted([(x1, y1), (y2, x2), (x3, y3)]) n_pos = tuple([*n_pos[0], *n_pos[1], *n_pos[2]]) if n_pos in v: continue v.add(n_pos..
