백준 문제풀이(파이썬)

이번 문제도 베르트랑 공준 문제처럼 먼저 소수를 모두 구한 뒤에 반복문을 이용해서 구해주면 될 것이다. 문제의 핵심은 2부터 증가하면서 둘다 소수이면 출력해주면 되는 것인데, 출력할 때 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력하고, 출력하는 소수는 작은 것부터 먼저 출력해야한다. 그러려면 min 변수와 gap 변수를 이용해서 gap을 매번 구해준 뒤 min과 비교해서 gap이 더 작으면 gap을 min에 넣어준 뒤 반복해서 비교해주면 되겠다. ##변수 선언 부분 T = 0 n = 0 min = 100000 gap = 0 save = 0 ##메인 함수 부분 if __name__ == "__main__": T = int(input()) prime = 10001 * [True] f..

이 문제는 입력값이 1~123,456 이므로 이중 for문을 이용하는 일반적인 소수 판별법으로는 시간 초과가 나올 것이 분명했다. 문제의 설명란에 에라토스테네스의 체로 풀어보자는 말이 있으므로 구글링을 해봤다. 위의 사진은 120까지의 자연수 중에서 소수를 모두 구하는 과정을 보여준다. 과정은 간단하다. 2의 배수를 모두 지우고, 그 다음엔 3의 배수를 지운다. 4는 이미 앞에서 2의 배수를 지울 때 지워졌기 때문에 4가 아닌 5로 넘어가서 5의 배수를 모두 지운다. 여기서 포인트는 위의 예에서 120까지의 소수를 구하는 것이 목적인데, 120 < 11^2 이므로 11까지만 이 과정을 반복해주면 된다. 이 과정을 반복하면 소수만 남는다는 것이 에라스토테네스의 체이다. 프로그래밍 언어로 구현하기는 생각보다..

소수를 구하는 법을 안다면 그렇게 어렵지 않은 문제이다. 입력 값도 10,000이하의 자연수이기 때문에 시간초과 걱정은 안해도 된다. M부터 N까지 반복문을 돌리면서 값이 소수인지 판별해주면 되겠다. 소수를 구할 때 2부터 나누어주면서 진행하기 때문에, 2가 소수라는 사실을 잊기 쉬우니 조심하자. 최솟값을 구할 때는 첫번 째 값일 때 즉, sum이 아직 0일 때 구한 값을 최솟값으로 초기값으로 설정해 준 뒤 그 뒤부터 비교를 해주면 된다. ##변수 선언 부분## M = 0 N = 0 min = 0 sum = 0 isRight = 0 ##메인 함수 부분## if __name__ == "__main__": M = int(input()) N = int(input()) for i in range(M, N+1):..

문제가 길어서 바로 흥미가 떨어질 수 있지만 생각보다 문제는 간단하다. x지점에서 y지점으로 이동하려면 y - x만큼의 거리를 이동해야하므로 입력 값의 크기는 중요하지 않고 두 값의 차이만 구해서 이용해주면 된다. 테스트 횟수 T를 입력받기때문에 T번만큼 반복문을 사용하면 될 것이다. k만큼 이동했으면 다음 이동 거리는 k-1, k, k+1중 하나만큼 이동할 수 있고, 어떻게 하면 최대한 적은 횟수만큼 이동하여 도착할 수 있는 지가 문제의 핵심이다. 거리가 크게 떨어져 있다고 생각해 보면 가능한 한 빨리 큰 숫자만큼 이동하게 만들어줘야하므로 초반에는 계속 k+1만큼 이동을 할 것이고, 너무 멀리까지 k+1을 하다보면 도착지점 바로 전에 1만큼 이동하지 못할 것이다. 그러므로 최대한 중간에서 k+1을 멈추..