밤이 블로그

a^3 + b^3 = c^3 + d^3 을 만족하는 100 이하의 자연수를 모두 찾아보자 a, b, c, d는 자연수이므로 a^3 + b^3의 결과도 어떤 자연수 x로 표현할 수 있다. 즉, 아래와 같이 표현할 수 있다. a^3 + b^3 = c^3 + d^3 = x 다시 바꾸어 말하면, 어떤 자연수 x는 위 조건을 만족하는 두 자연수의 쌍의 집합으로 표현할 수 있다. a^3 + b^3 = c^3 + d^3 = x1 [(a11^2 + b11^2), (a12^2 + b12^2), ...] = x2 [(a21^2 + b21^2), (a22^2 + b22^2), ...] = x3 [(a31^2 + b31^2), (a32^2 + b32^2), ...] = ... 이제 우리는 위 형태의 자료구조를 만들고 집합의 ..

BOJ#1963 소수 경로 * 문제https://www.acmicpc.net/problem/1963 * 풀이- 구하는 것 :두 소수 변환에 필요한 최소 변환 횟수 (최단 경로, 가중치 1이고 경우의 수가 많지 않으므로 BFS 탐색 가능) - 조건 : 4자리수, 소수로만 이동 가능, 중복 방문 x - 예를 들어 Test Case가 '1033 8179'인 경우 step = 0;1) 1033에서 한자리수를 변경해서 만들 수 있는 모든 소수들을 구한 후 Queue에 넣는다. (step = 1)2) step == 1인 Queue에 들어있는 모든 수에 대해 반복 (step = 2)3) step == 2인 Queue에 들어있는 모든 수에 대해 반복 (step = 3)....결국 step == n에서 8179를 찾게 ..