<링크>

https://www.acmicpc.net/problem/10973


<소스코드>

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


<풀이>

2018/07/24 - [알고리즘 풀이/기타] - 백준 10972 다음 순열


다음 순열 문제랑 비슷하다. 정렬 순서만 바꿔주면 된다.



얘도 라이브러리가 있다. prev_permutation( )

<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10000];
int main()
{
    int N;
    scanf("%d", &N);
    for (int i = 0; i<N; ++i) 
        scanf("%d", a+i);
    if(prev_permutation(a, a+ N))
        for (int i = 0; i<N; i++)
            printf("%d ", a[i]);
    else printf("-1");
}
 
cs



저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 13414 수강신청  (0) 2018.08.02
백준 13413 오셀로 재배치  (0) 2018.08.01
백준 10972 다음 순열  (1) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22
백준 9011 순서 :: 들짐승  (1) 2018.07.22

 

<링크>

https://www.acmicpc.net/problem/10972

 

<소스코드>

 

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

 

 

<풀이>


N이 10000이기 때문에 모든 순열을 하나하나 구해보면 N!의 시간이 걸리고 당연히 시간초과이다.그래서 하나하나 적어보며 규칙성을 찾았다.
1.

 맨 뒤에서부터 시작해서 내림차순이 끊기는 지점을 찾아낸다.

 

1 2 3 4

 

1 2 4 31 3 2 41 3 4 21 4 2 31 4 3 22 1 3 42 1 4 32 3 1 4...3 4 2 14 1 2 3...4 3 2 1

2.

 끊긴 지점에 있는 수가 증가되어야 하는데 조건이 있다. 앞에 나왔던 숫자는 제외하고, 뒤에 있는 숫자 중 크면서 가장 가까운 수로 바뀐다.

 

예를 들어보면

 

 

1이 증가되어야하는데 2로 될 수는 없다. 앞에 2가 있기 때문이다.

그럼 앞에 있는애들(2) 눈치 안보고 바뀔 수 있는 놈들은 뒤(4, 3)에 다 몰려있다.뒤에 있는 놈들 중에 누구로 바뀌면 될까 생각해봤는데 4로 바뀌면 안된다.2 1 x x 에서 바로 2 4 x x로 건너뛰는 셈이 되기 때문이다.
3으로 바뀌면2 3 x x 가 되고원래 뒤에있던 3의 자리에는 당연히 1이 들어가야한다.  즉, 맞바뀌게 된다. -> 2 3 4 1

3.

 숫자를 맞바꾸고 나면 끊긴 지점 뒤로 오름차순 정렬을 해준다.3 뒤로 오름차순정렬을 해서 2 3 1 4를 만든다.

4.

 끊긴 지점이 맨 앞이면, 맨 마지막 수열이므로 -1을 출력한다.

근데 사실 이런 고생을 안하고 풀수있는 방법이 있다. STL이 따로 있었다..

next_permutation( )

<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10000];
int main()
{
    int N;
    scanf("%d", &N);
    for (int i = 0; i<N; ++i) 
        scanf("%d", a+i);
    if(next_permutation(a, a+ N))
        for (int i = 0; i<N; i++)
            printf("%d ", a[i]);
    else printf("-1");
}
 
 cs

 

저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 13413 오셀로 재배치  (0) 2018.08.01
백준 10973 이전 순열  (0) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22
백준 9011 순서 :: 들짐승  (1) 2018.07.22
백준 8982 수족관1 :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/2725


<풀이>

한번 나왔던 기울기에 속하는 좌표는 다시는 보일수없다
x/y 가 기울기이다. 

예를 들면 x가 2, y가 8일때 기울기는 2/8이 되는데 이는 이미 1/4에서 나왔기 때문에 보일수없다. 
x가 3, y가 5일때는 같은 기울기가 나왔을 수 없기 때문에 보인다. 


정리하면 
1/y 
2/y 
... 
y/y 
중에서 좌표끼리 분수를 만들고 약분되면 그 좌표는 보일 수가 없다.  
이전에 이미 같은 기울기가 나왔다는 뜻이기 때문이다. 
따라서 분모와 분자의 최대공약수가 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
#include<stdio.h>
int ans[1001] = { 0,2 };
int gcd(int, int);
int main()
{
    for (int i = 2; i <= 1000; ++i)
    {
        int n = 0;
        for (int j = 1; j <= i; ++j)
        {
            if (gcd(i, j) == 1)
                ++n;
        }
        ans[i] = ans[i - 1] + n;
    }
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        printf("%d\n", ans[N] * 2 - 1);
    }
}
int gcd(int a, int b)
{
    while (a%b != 0)
    {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return b;
}
cs


저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 9011 순서 :: 들짐승  (1) 2018.07.22
백준 8982 수족관1 :: 들짐승  (0) 2018.07.22
백준 5624 좋은 수 :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/9011


<풀이>

내앞에 나보다 작은 수가 몇 개 있는지 주어지면 원래 수열을 찾는다.
맨 뒤부터 참조하면 된다.
맨 뒤에서 9라면 나는 10일 수 밖에 없다.
10
0 0 0 2 0 1 6 7 6 9 

맨뒤부터 숫자 그대로를 index로 사용하고 벡터에서 erase()하였다.
벡터에서 특정 위치의 원소를 erase하면 뒤에 있는 것들이 앞으로 한칸씩 땡겨오기 때문에 사용했다.
v : 1 2 3 4 5 6 7 8 9 10
v[9]=10 ->제거
1 2 3 4 5 6 7 8 9
v[6]=7 ->제거
1 2 3 4 5 6 8 9
v[7]=9 ->제거
1 2 3 4 5 6 8
v[6]=8 -> 제거
1 2 3 4 5 6
...
v[0]=6 ->제거

제거한값들을 거꾸로 나열하면 답이 된다.

IMPOSSIBLE이 뜨는 경우는 잘 모르겠어서 그냥 마지막 예제 입력을 위 과정대로 해봤더니
잘못된 입력이 있으면 접근하고자 하는 index가 현재 남아있는 벡터의 범위를 벗어나게 된다.
그냥 예제 따라해보면 쉽게 풀 수 있다.


<소스코드>

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
#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        vector<int> v;
        for (int i = 1; i <= N; ++i)
            v.push_back(i);
        int seq[101];
        int res[101];
        for (int i = 0; i < N; ++i)
            scanf("%d", seq + i);
        int check=1;
        for (int i = N - 1; i >= 0; --i)
        {
            int to = seq[i];
            if (to >= v.size())
            {
                printf("IMPOSSIBLE");
                check = 0;
                break;
            }
            res[i] = v[to];
            v.erase(v.begin() + to);
        }
        if (check)
            for (int i = 0; i < N; ++i)
                printf("%d ", res[i]);
        printf("\n");
 
 
    }
}
cs


저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22
백준 8982 수족관1 :: 들짐승  (0) 2018.07.22
백준 5624 좋은 수 :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/8982



<풀이>


1. 배열에 수평선의 각 index마다 총 깊이가 몇인지를 기록한다.


2. 구멍이 몇 열에 위치했는지 벡터에 집어넣는다.

깊이는 각 열마다의 총깊이이고, 시작깊이는 물이 시작되는 깊이이다. 맨 처음에는 물이 꽉차있는 상태이기 때문에 시작깊이는 모두 0이다.
구멍이 있는 열은 1, 3이다. 연속된 같은 깊이에서의 구멍은 여러 개가 있던, 어느 곳에 있던 상관없이 하나로 취급해도 된다. 따라서 그냥 3열이라고 했다. 4열에 구멍이 있다해도 똑같다.

3. 구멍이 있으면 그 열의 시작깊이는 총깊이와 같게 된다. 

적어도 해당구멍의 열의 물은 다 빠져나가기 때문이다. 그후 좌측, 우측으로 쭉 훑는데 어떻게 훑냐면


1
2
3
4
5
6
7
8
9
10
11
int cur = hall[i];
int h = depth[cur];
startDepth[cur] = h; //현재 구멍자리
//왼쪽 ㄱㄱ
for (int j = cur - 1; j >= 0; --j)
{
    if (h > depth[j])
        h = depth[j];
    if (startDepth[j] < h)
        startDepth[j] = h;
}
cs

h보다 깊이가 작으면 h를 그 값으로 갱신해준다. 이제 그보다 깊은 높이가 나와도 물을 뺄 수 없기 때문이다.
h보다 시작깊이가 낮으면 물을 뺄 수 있기 때문에 해당 열의 시작깊이를 h로 바꿔준다.
우측도 마찬가지로 진행한다.


h는 3으로 시작했고, 우측으로 훑을 때 녹색칸에서 h가 2로 바뀐다.

4. 위 과정들을 모든 구멍에 대해 반복한 후
5. 각 열마다 깊이-시작깊이 값을 모두 더해주면 남은 물의 양이 된다.


저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22
백준 9011 순서 :: 들짐승  (1) 2018.07.22
백준 5624 좋은 수 :: 들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바