29811 BOJ 2981: 검문 문제 링크 입력으로 들어올 수 있는 숫자의 최댓값이 10억임을 확인했지만 혹시나 싶어서 M = 2..min 까지 해봤지만 역시 틀렸었다. 근데 제출 결과가 틀렸습니다가 나온 걸 봐선 그냥 내 풀이 자체가 틀렸을 수도 있겠다. 이 문제는 위와 같은 이유로 다른 방법을 생각해야 하고 그 방법은 GCD를 활용하는 것이다. 입력이 5, 17, 23, 14, 83이면 가능한 M=3인데 입력을 다시 M과 엮어서 표현하면 5=1*3+2, 17=5*3+2, 23=7*3+2, 14=4*3+2, 83=27*3+2이다. 몫 부분을 제외하면 M과 R(나머지)은 공통되게 갖고 있는 것을 확인할 수 있다. 이 문제에서 기억해야 할 트릭은 나머지를 지우는 것이다. 예를 들어 17-5를 계산해보면 (5*3+2)-(1*3+2) = 4.. 2022. 5. 19. 이전 1 다음