피보나치 수 3




피보나치 수열은 다음과 같다.

0, 1, 1, 2, 3, 5, ...

n이 long long 범위 안으로 주어질 때 n번 째 피보나치 수를 구해라.



앞의 두 수를 더하면 피보나치 수가 생긴다. 하지만 n이 long long 범위이기 때문에 시간안에 구할 수 없다.

새로운 방법은 행렬을 사용하는 것이다.

f(n) = f(n-1) + f(n-2) // f(n-1) = f(n-1) 이므로,



여전히 행렬을 n-1번 곱해서 각 성분을 알야내야 한다는 점에서 시간복잡도는 줄지 않았다.

하지만 행렬이 곱셉에서 결합법칙이 성립한다는 점을 떠올린다면,

예를 들어 R^7 = R^4 * R^2 * R^1 로 분해할 수 있다는 것을 알 수 있다.


n-1은 long long 범위이므로 최대 2^64까지 커진다. 따라서 미리 2^0, 2^1, ... 2^63 까지 R의 제곱들을 구해놓으면,

log(n)시간에 답을 구할 수 있다. 위와 같이 4,2,1 제곱을 가져다 곱해주기만 하면 되기 때문이다.


소스는 다음과 같다.

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
59
60
61
62
63
64
#include <stdio.h>
#define mod 1000000
long long dp[64][2][2];
long long mat[2][2] = { {1ll,0ll},{0ll,1ll} };
long long n;
 
int main() {
    scanf("%lld", &n);
    if (n == 0) {
        printf("0");
        return 0;
    }
 
    if (n == 1) {
        printf("1");
        return 0;
    }
 
    dp[0][0][0] = 1ll, dp[0][0][1] = 1ll;
    dp[0][1][0] = 1ll, dp[0][1][1] = 0ll;
 
    for (int i = 1; i < 64; ++i) {
        dp[i][0][0] =
            ((dp[i - 1][0][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][0][1] =
            ((dp[i - 1][0][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][1]) % mod) % mod;
        dp[i][1][0] =
            ((dp[i - 1][1][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][1][1] =
            ((dp[i - 1][1][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][1]) % mod) % mod;
    } // 행렬의 2^i 제곱을 미리 구해놓는다.
 
 
    n--;
    for (int i = 0; (1ll << i) <= n; ++i) {
        if ((n & (1ll << i)) != 0) {
            long long tmp[2][2];
            for (int a = 0; a < 2; ++a)
                for (int b = 0; b < 2; ++b)
                    tmp[a][b] = mat[a][b];
 
            mat[0][0] =
                ((tmp[0][0] * dp[i][0][0]) % mod +
                (tmp[0][1] * dp[i][1][0]) % mod) % mod;
            mat[0][1] =
                ((tmp[0][0] * dp[i][0][1]) % mod +
                (tmp[0][1] * dp[i][1][1]) % mod) % mod;
            mat[1][0] =
                ((tmp[1][0] * dp[i][0][0]) % mod +
                (tmp[1][1] * dp[i][1][0]) % mod) % mod;
            mat[1][1] =
                ((tmp[1][0] * dp[i][0][1]) % mod +
                (tmp[1][1] * dp[i][1][1]) % mod) % mod;
        }
    }
 
    printf("%lld\n", mat[0][0]);
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

베르트랑 공준




소수를 에라토스테네스의 체를 사용해 판별해야 한다.

백준 1978 소수 찾기    (https://www.acmicpc.net/problem/1978)
백준 1929 소수 구하기 (https://www.acmicpc.net/problem/1929)


와 풀이를 겸한다.



에라토스테네의 체는 N보다 작거나 같은 모든 소수를 구하는 알고리즘이다.


방법은 다음과 같다.


2부터 시작하면서, 2의 모든 배수를 거른다.(2는 제외하고)


걸러지지 않은 가장 작은 수부터, 배수를 거르는 위의 작업을 반복한다.



위의 알고리즘은 N번 루프를 돌면서 배수들을 거른다.


루프 한 번당 배수들은 몇 개나 걸려질까?


위키신이 이르시길(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity)


평균적으로 log (log n) 번 걸러진다 하신다. 따라서 이 알고리즘의 시간복잡도는 n * log(log n) 이다.



베르트랑 공준은 임의의 n에 대해 (n, 2n] 구간엔 반드시 소수가 존재한다는 주장이다.


이를 검증하기 위해 여러 n이 주어지며, 매 번 소수의 갯수를 리턴해야 한다.


n이 몇 번이나 주어질지 상세되어있지 않으므로, 이미 부분합을 구해놓자.


그러면 n마다 psum[2 * n] - psum[n] 으로 (n, 2n]구간의 소수의 갯수를 선형시간에 알아낼 수 있다.



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
#include <stdio.h>
 
#define maxn 246912
int t;
 
bool is_not_prime[maxn + 1] = { true,true,false };
int psum[maxn + 1];
 
int main() {
    for (int i = 2; i <= maxn; ++i) {
        if (is_not_prime[i])
            continue;
        for (int j = i + i; j <= maxn; j += i)
            is_not_prime[j] = true;
    }
 
    for (int i = 2; i <= maxn; ++i) {
        psum[i] = psum[i - 1];
        if (!is_not_prime[i])
            psum[i]++;
    }
 
    while (1) {
        scanf("%d", &t);
        if (t == 0)
            break;
 
        printf("%d\n", psum[t * 2] - psum[t]);
    }
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

2609. 최대공약수와 최소공배수




문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 

24 18

예제 출력 

6
72




컴퓨터는 거대하고 빠른 계산기므로 이런 수학적 기초가 되는 연산을 빠르게 해낼 의무가 있다!


또한 컴퓨터를 다루는 사람은, 계산기에게 효율적인 명령을 내려야 한다.



당연히, 최대공약수를 알아야 최소공배수를 알 수 있다. 나의 상식선에선 그렇다.


초딩 때 최대공약수를 구하는 방법을 떠올려보면, 두 숫자 모두가 서로소가 될 때 까지, 두 수를 모두 나눌 수 있는 숫자로 계속 나눈다.


그러면 여태껏 나눈 숫자들을 곱하면 최대공약수고, 서로소 숫자 까지 곱하면 최소공배수다.



계산기에게 이런 계산을 맡기려면 어떻게 해야 할까?


물론 나이브하게 2부터 계속 키워가면서 나눠버리는 방법도 있다. 당연히 최악의 경우 두 수가 서로소면 O(n)이 걸릴테고.



그래서 유클리드가 만든 유클리드 호제법을 가져다 쓰기로 한다. 다음과 같다.


a>b인 두 수에 대해,   a%b = r 이라면, gcd(a,b) = (b,r) 이다.


예를 들어 gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = gcd(21, 0) = 21이다.



증명은 다음을 참고. 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#.EC.95.8C.EA.B3.A0.EB.A6.AC.EC.A6.98


또한 시간 복잡도는 여러 수학적 증명을 거쳐 O(log(n))임이 밝혀졌다. n의 비트수만큼 걸리는 것이다.



구현에 대해선, 당연히 재귀적으로 땡겨 쓸 직관이 생긴다!


코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
using namespace std;
 
int a, b;
 
int gcd(int a, int b) {
    if (a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}
 
int main() {
    scanf("%d %d", &a, &b);
    int g = a > b ? gcd(a, b) : gcd(b, a);
    printf("%d\n%d", g, a*b / g);
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

10973. 이전 순열




문제

1부터 N까지의 수로 이루어진 순열이 있다. 이 때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

예제 입력 

4
1 2 3 4

예제 출력 

-1

예제 입력 2 

5
5 4 3 2 1

예제 출력 2 

5 4 3 1 2




1. 접근


next_permutation 이 있드시, prev_permutation 도 있다!


전에 풀었던 수열 문제랑 비슷! http://js1jj2sk3.tistory.com/39



2. 풀이


하지만 stl에 의존하지 않기 위해서 원리대로 풀어보자.


다음 순열을 찾는 방법을 다 반대로 하면 된다!


오른쪽이 전부 내림차순(다음) -> 오름차순(이전) 이 아니게 되는 첫 숫자를 뒤에서 부터 찾고,

그 숫자보다 큰(다음) -> 작은(이전) 숫자를 뒤에서 부터 찾아서 서로 바꾼다.


나머지는 오름차순(다음) -> 내림차순(이전)으로 정렬한다




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
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
 
int n, i, k, arr[10000];
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }
 
    if (n == 1) {
        printf("-1");
        return 0;
    }
 
    int p = n - 1;
 
    while (arr[p - 1] < arr[p]) {
        p--;
        if (p == 0)
            break;
    }
 
    if (p == 0) {
        printf("-1");
        return 0;
    }
        
    for (k = n - 1; arr[p - 1] < arr[k]; --k);
 
    int tmp = arr[p - 1];
    arr[p - 1] = arr[k];
    arr[k] = tmp;
 
    sort(arr + p, arr + n, greater<int>());
 
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

10972 다음 순열



문제

1부터 N까지의 수로 이루어진 순열이 있다. 이 때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

예제 입력 

4
1 2 3 4

예제 출력 

1 2 4 3

예제 입력 2 

5
5 4 3 2 1

예제 출력 2 

-1




1. 접근


next_permutation 쓰면 걍 끝날 문제!


전에 풀었던 순열 순서 문제 http://js1jj2sk3.tistory.com/39 보다 더 간단하다.



2. 풀이


한 번 상기시키는 김에 next_permutation의 원리대로 짜보았다.


오른쪽이 전부 내림차순이 아니게 되는 첫 숫자를 찾고, 그 숫자보다 큰 숫자를 뒤에서부터 찾아서 처음 발견되는 숫자와 스위치하면 된다.


나머지는 오름차순으로 정렬해준다.



 

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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, i, k, arr[10000];
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    if (n == 1) {
        printf("-1");
        return 0;
    }
 
    int p = n - 1;
 
    while (arr[p - 1] > arr[p]) {
        p--;
        if (p == 0)
            break;
    }
 
    if (p == 0) {
        printf("-1");
        return 0;
    }
        
    for (k = n - 1; arr[p - 1] > arr[k]; --k);
 
    int tmp = arr[p - 1];
    arr[p - 1] = arr[k];
    arr[k] = tmp;
 
    sort(arr + p, arr + n);
 
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

9742. 순열


문제

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다.

  1. 2 3 5
  2. 2 5 3
  3. 3 2 5
  4. 3 5 2
  5. 5 2 3
  6. 5 3 2

각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다.

서로 다른 숫자와 문자로 이루어진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어진다.

출력

각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 만약, 해당하는 순열이 없는 경우에는 "No permutation"을 출력한다.

예제 입력 

235 4
bein 20
123456 700
mnpqr 130
tuvwxyz 4000

예제 출력 

235 4 = 352
bein 20 = nbie
123456 700 = 651342
mnpqr 130 = No permutation
tuvwxyz 4000 = ywuxvzt



1. 접근


순열을 만드는 규칙이 정해져있고, 몇 번째 순열을 출력해야 하는지 주어진다.


규칙은, 우리가 보통 경우의 수를 찾는 방법과 동일하다.


1,2,3,4 라면, 첫 번째 자리에 가장 작은 1을 적는다. 두 번째 자리엔 2,3,4 가 올 수 있다. 그 중 가장 작은 2을 적는다. ...


첫 번째 자리의 경우를 모두 적었으면, 그 다음으로 작은 2를 적고 동일한 과정을 반복한다.



당연히 (글자길이!)를 넘어가는 k번 째 순열을 존재하지 않으므로, 전처리로 팩토리얼을 미리 계산해주면 없는 경우는 쉽게 알 수 있다.


다만 위와같이 해당 순열을 빠르게 찾으려면 어떻게 해야할까?




2-1). 풀이 1


놀랍게도 알고리즘 헤더에는 위와 같은 문제를 해결해주는 함수가 기존재한다.


바로 next_permutation(iterator first, iterator last) 인데, 이 함수는 [first, last) 범위 안의 원소들을 다음 "사전 순서"로 정렬해준다.


사전 순서란 우리의 규칙과 동일하게 적용된다.


영어사전의 단어들이 어떤 순서로 소개되는지 생각해보면 된다.



그러면 간단하게 함수호출로 문제를 풀 수 있을 것이다. k번 째 순열을 찾기 위해서 함수를 k번 호출하면 될 것이다.



2-2). 풀이 2


그러면 저 함수는 어떻게 구현되어 있는 걸까?


다음에서 정보를 얻었다.


https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation



사전 순으로 1,4,3,2 의 다음 순열은 2,1,3,4 이다.


눈치 깔 수 있는 것은, 1의 오른쪽이 전부 내림차순이면 1의 자리수는 다음으로 큰 수로 바뀌고, 나머지는 오름차순으로 다시 정렬된다는 것이다.


마찬가지로, 1,3,4,2의 다음 순열은 1,4,2,3 이다.


오른쪽이 전부 오름차순이 아니게 되는 첫번째 원소는 3이었다. 그러면 3은 다음으로 큰 수로 바뀌고, 나머지는 오름차순으로 다시 정렬된다.



그러면 구현해야 할 것은 두 가지다. 


1. 오름차순이 아니게 되는 원소를 뒤에서 부터 찾은 다음, 그 원소보다 다음으로 큰 수를 찾아야하고


2. 나머지를 오름차순으로 정렬해야 한다.



1번은 쉽게 할 수 있다. 우리가 찾은 원소는 오른쪽이 오름차순이 아니게 되는 첫 원소이므로, 다음으로 큰 수는 뒤에서 부터 원소보다 처음으로 큰 수다.


2번은 그냥 sort를 쓸 수도 있겠지만, 다음과 같이 더 빠르게 수행할 수 있다.



먼저 1번에서 찾은 원소와 다음으로 큰 수를 서로 바꾼다. 1,3,4,2 였다면 3과 4를 바꿔서 1,4,3,2가 되었을 것이다.


우리가 찾은 원소는 오른쪽이 오름차순이 아니게 되는 첫 원소이므로, 나머지 두 자리수는 자명히 내림차순이다. 따라서 역순으로 뒤집어 주면 된다.


-> 1,4,2,3



1,4,5,3,2 의 다음 사전 순 순열은 1,5,2,3,4 이다. 1번을 수행하고 찾은 원소는 4다. 4보다 큰 수는 5임을 뒤에서 부터 찾을 수 있다.


4와 5를 바꾼다. 1,5,4,3,2 가 된다. 당연히 5의 오른쪽은 전부 내림차순이다. 오른쪽을 전부 뒤집어주자. -> 1,5,2,3,4 




2-3) 풀이 3


사실 수학적으로도 풀 수 있다.


1,2,3,4 로 4자리의 순열이라면, 총 4! = 24의 경우가 있는데, 이는 크게 첫 자리별로 4개의 집합으로 분류할 수 있다.


또 각각의 집합 안에서, 남은 세 자리 중에 첫 자리(실제론 두번째 자리)별로 3개의 집합으로 분류할 수 있다.



예를 들어, a,b,c,d 의 17번째 사전 순 순열을 알고 싶다면, 첫 자리별로 3! = 6 의 경우를 갖고 있으니까 16 / 6 = 2다.


(모듈러 연산을 위해 0, 1, 2, ... 순으로 순서를 매기자.)


이는 첫 자리가 arr[2] = c 임을 알려준다.



남은 세 자리에 대해 생각해보면 총 6가지 경우가 있으니까 16 % 6 = 4다. 이 말은 그 집합 안에서 다섯번째 순열이란 뜻이다.


4를 2!으로 나누면 2가 나온다. 이 말은 두 번째 자리가 남은 a, b, d 중 arr[2] = d 라는 뜻이다.



남은 두 자리에 대해 생각해보면 총 2 가지 경우가 있으니까 4 % 2 = 0이다. 이는 그 집합 안에서 첫번째 순열이란 뜻이다.


0을 1!으로 나누면 0이 나온다. 이는 세 번째 자리가 남은 a, b 중 arr[0] = a 라는 뜻이다.



이제 구현은 재귀적으로 할 수 있다.


자리 수를 채워나가면서 맨 앞자리를 가리키는 포인터를 전진시키면서 넘겨주면 된다. 



3-1) 코드 1


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
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int fact[12] = { 1, };
 
int main() {
 
    for (int i = 1; i <= 10; i++)
        fact[i] = fact[i - 1] * i;
 
    string a;
    int n;
 
    while (cin >> a >> n) {
 
        cout << a << " " << n << " = ";
 
        if (n > fact[a.length()]) {
            cout << "No permutation" << endl;
            continue;
        }
 
        int cnt = 0;
        do {
            cnt++;
            if (cnt == n) {
                cout << a << endl;
                break;
            }
        } while (next_permutation(a.begin(), a.end()));
    }
 
    return 0;
}
cs



3-2) 코드 2


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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n, k;
int fact[12];
int num[11];
char str[20];
 
bool next_per(int x, int y) {
    if (x == y)
        return false;
 
    int i = y;
 
    while (1) {
        int j = i;
        --i;
 
        if (num[i] < num[j]) {
            int k = y + 1;
            
            while (!(num[i] < num[--k]));
 
            int tmp = num[i];
            num[i] = num[k];
            num[k] = tmp;
 
            for (int t1 = j, t2 = y; t1 <= (j + y) / 2; ++t1, --t2) {
                int tmp = num[t1];
                num[t1] = num[t2];
                num[t2] = tmp;
            }
            return true;
        }
 
        else if (i == x) {
            for (int t1 = x, t2 = y; t1 <= (x + y) / 2; ++t1, --t2) {
                int tmp = num[t1];
                num[t1] = num[t2];
                num[t2] = tmp;
            }
            return false;
        }
    }
}
 
int main() {
    fact[0] = 1;
    for (int i = 1; i <= 10; i++) {
        fact[i] = fact[i - 1] * i;
    }
        
    while (~scanf("%s %d", str, &k)) {
        n = strlen(str);
        for (int i = 0; i < n; ++i)
            num[i] = i;
        int cnt = 0;
 
        printf("%s %d = ", str, k);
        if (k > fact[n] || k <= 0)
            puts("No permutation");
        else {
            while (++cnt != k)
                next_per(0, n - 1);
 
            for (int i = 0; i < n; ++i)
                printf("%c", str[num[i]]);
            puts("");
        }
    }
    return 0;
}
cs



3-3) 코드 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n, k;
int fact[12] = { 1, };
char str[20];
 
void func(char *s, int x, int f) {
    if (f < 1) return;
 
    int i = x / fact[f - 1];
    int last = s[i];
 
    while (i-- > 0)
        s[i + 1] = s[i];
    
    s[0] = last;
 
    func(s + 1, x % fact[f - 1], f - 1);
}
 
int main() {
    for (int i = 1; i <= 10; i++)
        fact[i] = fact[i - 1] * i;
 
    while (scanf("%s %d", str, &k) != EOF) {
        n = strlen(str);
 
        printf("%s %d = ", str, k--);
 
        if (k >= fact[n] || k < 0)
            puts("No permutation");
 
        else {
            func(str, k, n);
            puts(str);
        }
    }
 
    return 0;
}
cs



4. 후기


처음엔 계속 배열을 두고 쓴 자리수를 체크체크하는 무지막지한 방법으로 124ms로 들어왔었다.


풀이 1 : 12 ms


풀이 2 : 20 ms


풀이 3 : 0 ms

'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11

+ Recent posts

티스토리툴바