접근처음에는 ((A % M) + (B % M)) % M = (A+B) % M 을 사용하는 문제라고 생각했다. A + B == C일 때, ((A % M) + ((C - A) % M)) % M = C % M를 활용하면 될 것 같았는데, 수가 최대 1,000,000,000까지이므로 인덱스를 어디로 잡는지가 문제였다. 제한 시간이 초과되었고, 알고리즘을 확인해보니 유클리드 호제법이 있었다. 이전에도 몇 번 접했지만 자주 쓰지 않을 거라고 판단해서 그 때 그 때마다 찾아서 확인했었다. 자주 접하게 되어서 아예 에라토스테네스의 체처럼 기억을 해둘 필요를 느꼈다. 유클리드 호제법두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r gcd(a, b) = gcd(b, r) 반복문 방식def euc..
Problem Solving
접근팀원 구성 점수 아래 요소들의 합계이다.(X, Y), (Y, Z), (X, Z) 의 천간 관계 점수, 지지 관계 점수X, Y, Z의 실력 값의 합계그렇다면 결국 메모는 필요한데 배열과 dict를 고민하던 중 조합을 사용해야 하는데 N이 10^6까지 가능하므로 비트마스킹을 쓰기에는 너무 크다고 판단하여 dict를 사용하기로 했다. dict를 사용해서 2가지 조합을 미리 만들고 여기서 한 명을 더 추가하는 식으로 하려고 했었는데 이를 구현하지 못했다. 결국 시간이 꽤 흘렀고 알고리즘을 확인해보니 비둘기집 원리 문제였다. 풀이비슷한 유형을 풀어보고 싶다면 이 문제를 풀어보자. 비둘기집 원리란 비둘기 집이 N개있고, N 보다 큰 M 마리의 비둘기가 있다고 가정하자. 이 때 최소 한 마리 이상의 비둘기는 다른..
풀이아래에서 다루는 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), (..
풀이 방법을 떠올리다가 처음에는 배열을 사용한 DP로 시도했는데, N이 10^18까지 가능해 배열로는 풀 수가 없는 문제였다. N이 워낙 크다보니 BFS로도 풀지 못할 것이라 생각해 시도조차 하지 않았었고 도저히 모르겠어서 알고리즘을 확인했는데 BFS가 있어서 놀랐다. 결국 BFS가 돌아갈 수 있었던 이유는 메모리가 1024byte로 모든 수를 메모이제이션 하기에는 부족하지만, BFS 큐 사이즈를 감당하기에는 충분했기 때문인 것 같다. BFS 특성상 모든 수를 다 돌아보지 않고 가장 빨리 도달하는 경우만 살펴보기 때문이다. 관건은 "-1연산을 최소화할 수 있는가?"인 것 같다.BFS 풀이추가적으로 새로 알았던 점은 defaultdict를 사용할 때 그동안 관습적으로 int를 넣어줬었는데 여기에 커스텀 메..
