BOJ 13171 - A 문제 링크 https://www.acmicpc.net/problem/13171 문제 해결 1. Successive Squaring Method를 이용해서 문제를 해결해야한다. ( A와 X 모두 10^18이므로) 2. 문제에 해결 방법이 나와있는 쉬운 문제 주의할 점 || 생각해볼 점 1. 반드시 A도 나머지 연산을 해야한다. ( 곱하는 단계에서 오버플로우가 생길 수 있다.) 2. 곱하기 연산을 할 수도 있지만, 이진수로 표현함을 이용해서 비트 연산을 하는 것이 더욱 효율적이다. 참고 Successive Squaring Method : http://mathworld.wolfram.com/SuccessiveSquareMethod.html ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2602 - 돌다리 건너기 문제 링크https://www.acmicpc.net/problem/2602 문제 해결1. " 한 방향으로 이동 + 모든 경우의 수 " 에서 Dynamic Programming으로 해결 2. dp[i][j][k] = i (천사 또는 악마) 행, j (돌다리) 열을 밟았을 때 두루마리 속 k번째 문자를 밟은 경우의 수. 3. Top-down 형태로 풀려고 애썼다. 주의할 점 || 생각해볼 점1. Dp 배열을 만드는 것이 어려웠다. 완전 탐색 하면서 놓치지 않아야 할 정보를 담아야한다. 2. 기저 조건을 설정하는 것이 익숙하지가 않았다. 가령 최대 인덱스가 k라면, k+1에서 기저 조건을 수행. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2436 - 공약수 문제 링크https://www.acmicpc.net/problem/2436 문제 해결1. 구하려는 두 수를 a, b로 놓는다. 2. a == (GCD*x), b == (GCD*y) 이므로, measure = x*y (x*y == LCM/GCD) 3. measure의 (x,y)쌍을 찾되 합이 가장 작은 것을 찾아야하므로 시간을 단축하기 위해, sqrt(measure)부터 찾는다. 주의할 점1. LCM == GCD*x*y가 성립하기 위해선 반드시 x와 y가 서로소임을 보여야한다. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 ··· 22 23 24 25 26 27 28 ··· 32 다음