[백준/C++] 1193번. 분수찾기
문제 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 1. 첫 번째 풀이 사고 과정 - 대각선이지만 굳이 대각선으로 볼 필욘 없다. 1/1을 한 줄, 1/2와 2/1을 한 줄, 1/3과 2/2와 3/1을 한 줄. 이렇게 계단처럼 쌓을 수 있다. - 우린 각 줄의 첫번째, 즉 1/N이 몇 번째부터 시작하는지 알 수 있다. 1, 2, 4, 7, 11. 정확히는, 해당 줄의 앞이 몇 번으로 끝났는지 알 수 있다. 0, 1, 3, 6, 10, 15, 21. 익숙한 1부터 n까지의 합. 이 번호들을 기준 번호라고 하자. - 그러니 우선 1부터 더해가며, X를 넘지 않는 값까지 더하면, 마지막에 더한 값으로부터 N을 알 수 있다. 만약 12라면 10에..
[C++] 소인수분해: 두 소수 p, q의 곱 n이 주어질 때, p, q 알아내기
이 사람은 왜 이런 짓을 했는가? 시험 기간인데 시험 공부는 하기 싫어서 간단한 알고리즘을 짜봤다. 문제 RSA 알고리즘을 배울 때 꼭 한 번씩 들어보는 말. 두 소수 p, q가 주어졌을 때 n을 계산하는 건 매우 단순한 일이지만, 두 소수의 곱 n이 주어졌을 때 p, q를 알아내는 건 NP 문제다. 그래서 어떻게 하면 n이 주어졌을 때 p, q를 빠르게 알아낼 수 있을까?라는 질문이 샤워 도중 떠올랐고, 샤워하면서 한 생각을 코드로 옮겨봤다. 알고리즘 거창한 문제에 비해 내 생각은 단순했다. twosum 문제를 좀 응용하면 되지 않을까? 정확한 사고 과정은 아래와 같았다. 두 소수 p, q를 곱한 n이 있다면, p와 q는 sqrt(n)에서 비슷하게 떨어져 있지 않을까? 3 * 13, 7 * 13을 해봄..
