반응형 GCD1 [SWEA/C++] 서로소 그리드 (No. 20731) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 GCD를 이용하면 쉽게 풀 수 있는 문제다. 문제를 보면 GCD(k+i, k+j)가 1이면 1, 아니면 ?를 N*N 배열에 기록한다.이때, 이 배열의 조건에 만족하는 k가 존재하는지 판단하는 문제다. 이 문제에서 중요한 점은 K의 범위가 정해져 있지 않기 때문에 모든 조건에 맞는 K가 있는지 확인하면 된다. 그렇다고 모든 K에 대해 탐색할 수는 없다. 그러면 GCD(k+i, k+j)를 어떻게 표현할 수 있을까? i > j의 조건을 만족하는 경우에 GCD(k+i, k+j)가 1이 아니라면 GCD(k+i, i-j.. 2024. 6. 19. 이전 1 다음 반응형
