백준 2526번: 싸이클
https://www.acmicpc.net/problem/2526
1. 문제
두 자연수 N과 P를 가지고 다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는 숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다.
이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다. 예를 들어서, N=67, P=31인 경우를 생각해보자. 처음 출력되는 숫자는 67이고, 두 번째로 출력되는 숫자는 67*67 = 4489를 31로 나눈 나머지 25이다. 다음에는 25*67 = 1675를 31로 나눈 나머지 1, 다음에는 1*67 = 67을 31로 나눈 나머지 5가 차례대로 출력된다. 다음에는 5*67 = 335를 31로 나눈 나머지 25가 출력되는데, 이 수는 이미 이전에 출력된 수이다. 이 과정을 그림으로 보이면 다음과 같다.
2. 알고리즘
[Figure 1]
1차원 배열을 선언하여 현재 계산할 값을 대입 한다.
싸이클에 입력받은 n과 p 의 값으로 다음 값을 계산 한다.
예제에서는 N = 67, P = 31 임으로 계산 공식에 의해 다음 수는 25가 된다.
[Figure 2]
1차원 배열에 다음 인덱스에 현재 계산할 값을 대입 한다.
figure 1 에 동작을 반복 한다.
[Figure 3]
1차원 배열에 다음 인덱스에 현재 계산 할 값을 대입 한다.
figure 3 도 figure2 처럼 figure 1 에 동작을 반복 한다.
[Figure 4]
figure1 동작을 반복 한다.
[Figure 5]
위 동작을 반복 하다 보면 순환되는 영역을 확인 할 수 있다.
계산된 값을 배열에 대입 하면서 순환되는지 확인 하기 위해 검사코드를 추가 해야 한다.
1 2 3 4 5 6 7 8 | for (int i = 0; i < sol; i++) { // 현재 계산 된 값이 순환 되는지 확인 한다. if (arr[i] == cand) { // 순환이 된다면 현재 index로 부터 sol(계산된 수를 저장한 배열의 인덱스) 차이 값을 출력 한다. cout << sol - i << "\n"; return 0; } } | cs |
3. 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <iostream> #include <sstream> #include <string> #include <algorithm> #include <functional> #include <vector> #include <list> #include <queue> #include <deque> #include <map> #include <set> #include <stack> #include <cstring> #define MAX_SIZE 100 #define INF 0x7fffffff using namespace std; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int reverse(int x) { int rev = 0; while(x != 0){ rev = rev*10 + x%10; x = x/10; } return rev; } int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n, p; cin >> n >> p; int arr[100] ={0,}; int sol = 0; arr[sol++] = n; int cand = n; while (true) { cand = (cand * n) % p; for (int i = 0; i < sol; i++) { // 현재 계산 된 값이 순환 되는지 확인 한다. if (arr[i] == cand) { // 순환이 된다면 현재 index로 부터 sol(계산된 수를 저장한 배열의 인덱스) 차이 값을 출력 한다. cout << sol - i << "\n"; return 0; } } arr[sol++] = cand; } return 0; } | cs |