<링크>

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



<dfs_소스코드>

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
#include<stdio.h>
int N;
int dfs(int);
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &N);
        printf("%d\n",dfs(0));
    }
}
int dfs(int sum)
{
    if (sum > N)
        return 0;
    if (sum == N)
        return 1;
    int cnt = 0;
    for (int i = 1; i <= 3; ++i)
    {
        cnt+=dfs(sum + i);
    }
    return cnt;
}
cs


<풀이>

dfs로 해도 되고, dp로 풀어도 된다.

n이 최대 10이기 때문에

dfs로 해도 되지만

n이 커지면 dp로 풀어야 된다.



<dp_소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
int dp[11] = { 1, };
int main()
{
    for(int i=1;i<=10;++i)
        for (int j = i - 1; j >= i - 3; --j)
            if (j >= 0)
                dp[i] += dp[j];
    int T,N;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &N);
        printf("%d\n", dp[N]);
    }
}
cs


<풀이>

5를 만들수있는 경우의 수는

4에서 1을 추가한 경우,

3에서 2를 추가한 경우,

2에서 3을 추가한 경우

로 나타낼 수 있으므로

4를 만드는 경우의 수 + 3을 만드는 경우의 수 + 2를 만드는 경우의 수이다.

앞에서부터 쭉쭉 만들어나가면 된다.




저작자표시

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

백준 9084 동전  (0) 2018.08.17
백준 1005 ACM Craft  (0) 2018.08.06
백준 14501 퇴사 :: 들짐승  (1) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace std;
typedef unsigned long long ull;
void setFac();
ull fact[21] = { 1, };
int main()
{
    int N,T;
    setFac();
    scanf("%d", &N);
    while (~scanf("%d", &T))
    {
        if (T == 1)
        {
            ull k;
            scanf("%llu", &k);
            vector<int> first;
            for (int i = 1; i <= N; ++i)
                first.push_back(i);
            vector<int> ans;
            
            --k;
            int p = N - 1;
            while (p>=0)
            {
                int div = k / fact[p];
                ans.push_back(first[div]);
                first.erase(first.begin() + div);//벡터지우기
                k = k % fact[p];
                --p;
            }
            for (int i = 0; i < N; ++i)
                printf("%d ", ans[i]);
            printf("\n");
        }
        else
        {
            int tmp;
            ull ans = 0;
            vector<int> v;
            for (int i = 0; i < N; ++i)
            {
                scanf("%d", &tmp);
                v.push_back(tmp);
            }
            for (int i = 0; i < N-1; ++i)
            {
                int cnt = v[i]-1;
                for (int j = 0; j <= i; ++j)
                {
                    if (v[j] < v[i])
                        --cnt;
                }
                if (cnt > 0)
                    ans += cnt * fact[N - i - 1];
                    //팩토리얼 더해
            }
            printf("%llu\n", ans + 1);
        }
    }
}
void setFac()
{
    for (int i = 1; i <= 20; ++i)
        fact[i] = fact[i - 1] * i;
}
cs


<풀이>

1. k번째 순열 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ull k;
scanf("%llu", &k);
vector<int> first;
for (int i = 1; i <= N; ++i)
    first.push_back(i);
vector<int> ans;
--k;
int p = N - 1;
while (p>=0)
{
    int div = k / fact[p];
    ans.push_back(first[div]);
    first.erase(first.begin() + div);//벡터지우기
    k = k % fact[p];
    --p;
}
cs

일단 벡터에 1부터 N까지 집어넣는다.

초기에는 {1,2,3,4}이다.

그 후 각 자리마다 몇번째 블록에 해당하는지 알아내면 된다.



k=10일때

맨 앞 숫자의 index를 구하면

k / 3! 이 된다. 왜냐면 

1로 시작하는 경우 3!개, 2로 시작하는 경우 3!개, 3으로 시작하는 경우 3!개, 4로 시작하는 경우 3!개가 있기 때문이다.

그럼 k / 3! 의 몫이 곧 맨 앞의 숫자의 index가 된다.


● 첫번째 숫자 구하기

10 / 3! = 1이므로

{1,2,3,4} 의 [1]은 2가 된다.

그 후 2는 이미 나왔으므로 나중에 index를 구했을 때 지장을 주지 않기 위해 빼버린다.

{1,3,4}가 된다.


● 두번째 숫자 구하기

3!단위의 블록이 정해졌으면 그 안에서의 index을 또 찾기 위해 10%3!을 해서 4를 만든다.

4 / 2! = 2이므로

{1,3,4} 의 [2]는 4가 된다. 4를 빼버리고 {1,3}으로 만든다.


● 세번째 숫자 구하기

4%2!을 해서 0을 만들고

0/1! = 0이므로

{1,3}의 [0]은 1이 된다. 1을 빼버리고 {3}으로 만든다.


● 마지막 숫자 구하기

{3}의 [0]은 3이다.


2 4 1 3 이 답이 된다.



2. 순열 입력받아 k 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int tmp;
ull ans = 0;
vector<int> v;
for (int i = 0; i < N; ++i)
{
    scanf("%d", &tmp);
    v.push_back(tmp);
}
for (int i = 0; i < N-1; ++i)
{
    int cnt = v[i]-1;
    for (int j = 0; j <= i; ++j)
    {
        if (v[j] < v[i])
            --cnt;
    }
    if (cnt > 0)
        ans += cnt * fact[N - i - 1];
        //팩토리얼 더해
}
printf("%llu\n", ans + 1);
cs


각 숫자를 보면서 내 앞에 몇 개가 있는지 본다. ( 2,4,3,1 )

● 첫번째숫자 : 2

1 x x x 인 애들을 일단 건너뛰어야 한다.

따라서 (2-1) * 3! = 6


● 두번째숫자 : 4

두번째 숫자부터는, 내 앞에 나왔던 숫자 중에 나보다 작은 숫자가 이미 등장했으면 경우의 수로 셀 수 없기 때문에

건너뛸 수 있는 경우의 수에서 제외시킨다.

2 1 x x : 2개

2 2 x x : 2개

2 3 x x : 2개

총 6개를 건너뛰어야 될 것 같지만 2 2 x x 는 순열로 불가능하기 때문이다.


따라서 ( 4 -1- 1 )* 2! = 4


● 세번째숫자 : 3

2 4 1 x 는 가능하지만

2 4 2 x 는 불가능하기 때문에


( 3 - 1 - 1 ) * 1! = 1


6+4+1 = 11이 답이 된다.



저작자표시

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

백준 1110 더하기 사이클  (0) 2018.08.29
백준 1652 누울 자리를 찾아라  (0) 2018.08.28

<링크>

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



지금으로부터 6달 전, 2018년 1월 5일에 풀었었는데 이 때에 비해 실력이 얼마나 늘었는지 궁금해서

똑같은 문제를 또 봤다. 많이 틀리고 개고생했던 기억이 난다.


<2018.01.15 소스코드>

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
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        // 61453
        // 7 8 9
        Scanner in = new Scanner(System.in);
        String num = in.next();
        int channel = Integer.parseInt(num);
 
        int K = in.nextInt();
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < 10; ++i)
            list.add(i);
 
        for (int i = 0; i < K; ++i)
            list.remove(new Integer(in.nextInt()));
        // list정렬
        Collections.sort(list);
        int nogada = Math.abs(channel - 100);
    
        if (K == 10) { // 칠수있는 번호가 하나도없을시 (다고장)
            System.out.println(Math.abs(channel - 100));
            return;
        }
 
        int mini = channel;
        String min = null;
        boolean check1 = false,check2=false;
        while (mini >= 0) {
            min=Integer.toString(mini);    
            if(channel-mini+min.length()>=nogada)
                break;
        
            check1 = true; // 성공했다고 가정
            for (int j = 0; j < min.length(); ++j) {
                int n = min.charAt(j) - '0';
                if (list.indexOf(n) == -1) {
                    check1 = false;
                    break;
                } // 실패
            }
            if (check1 == true)
                break;
            else
                --mini;
        }
        int maxi=channel;
        String max;
        while (true) {
            max=Integer.toString(maxi);    
            if(maxi-channel+max.length()>=nogada)
                break;
            check2 = true; // 성공했다고 가정
            for (int j = 0; j < max.length(); ++j) {
                int n = max.charAt(j) - '0';
                if (list.indexOf(n) == -1) {
                    check2 = false;
                    break;
                } // 실패
            }
            if (check2 == true)
                break;
            else
                ++maxi;
        }
        mini=channel-mini+min.length();
        maxi=maxi-channel+max.length();
        
        int result=nogada;
        if(maxi<result && check2){
            result=maxi;
        }
        if(mini<result && check1){
            result=mini;
        }
        System.out.println(result);
        
        // 만들수있는숫자 i가 나옴
 
    }
}
 
cs


<풀이>

뭐저렇게 복잡해보이는지 잘 모르겠다. 꼴보기 싫어서 그냥 새로 풀었다.




<2018.07.26 소스코드-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
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
vector<int> v;
int seq[6];
int X[10];
int ans, N, M;
void check();
void dfs(int);
int main()
{
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i)
    {
        int n;
        scanf("%d", &n);
        X[n] = 1; // 1고장난애들
    }
    ans = abs(N - 100);
    v.push_back(0); //0은 무조건 추가, 자리수관리용
    for (int i = 1; i < 10; ++i)
        if (!X[i])
            v.push_back(i); //누를수있는 버튼을 벡터에 추가
    dfs(0);
    printf("%d",ans);
}
void dfs(int len)
{
    if (len == 6)
    {
        check();
        return;
    }
    for (int i = 0; i < v.size(); ++i)
    {
        seq[len] = v[i];    
        dfs(len + 1);
    }
}
void check()
{
    int i = 0;
    int cnt = 6;
    while (i < 5 && seq[i] == 0) //앞에 붙은 0들을 제거
    {
        ++i;
        --cnt;
    }
    int channel = 0;
    while(i<6)
    {
        if (seq[i] == 0 && X[0]) //앞의 0을 다 제거했으므로 이제 사이에 나오는 0은 0버튼이 고장났는지 여부에 따라 갈림
            return;
        channel += seq[i] * pow(10, 5 - i);
        ++i;
        
    }
    
    if (abs(N - channel) + cnt < ans)
        ans = abs(N - channel) + cnt;
 
}
cs
<풀이>

리모콘 버튼을 하나 선택하고 다음자리 수를 재귀를 돌렸다. 최대 6자리까지만 했다.

N의 최대입력값이 500000이기 때문에 999900 이상되는 수부터는 +,-를 이용해서 오는건, 100번에서 +,-만 이용해서 오는 것보다 구리기 때문이다.


시간복잡도는 10^6이다.


맨 처음 채널에 100이기 때문에 100에서부터 원하는 채널 N까지 +,-를 이용해 가는 값, 즉 |N-100| 으로 최솟값을 일단 정해놓고 고장이 안난 버튼으로 재귀를 돌다가 depth가 6이 되면 최솟값을 갱신했다.


예를 들어

고장난 번호가 3,4,5,6,7,8,9 일 때 가능한 번호는 0,1,2이고


000000

000001

000002

...

000012

...

222220

...

222222

이렇게 모두 체크해본다.


000012를 체크하면, 앞의 0은 누른 횟수로 치지않고 2번 누른 것으로 한다.


근데 여기서 0 버튼이 고장나면 문제가 발생한다.

고장이 안난 버튼으로만 재귀를 돌렸기 때문에

111111

111112

...

222222 이렇게 체크하게 되는데

그럼 6자리가 아닌 채널들은 체크를 못하게된다.

그래서 0은 무조건 재귀돌릴 때 추가하고,  체크할 때 걸러내게끔 했다

000012 -> 얘는 앞자리채우기로써 0이 들어온거니까 : ㅇㅋ

011012 -> 중간에 유효숫자로써 0이 들어온거니까 : ㄴㄴ



<2018.07.26 소스코드-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
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string>
int check(int);
using namespace std;
int X[10];
int ans, N, M;
int main()
{
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i)
    {
        int n;
        scanf("%d", &n);
        X[n] = 1; //고장난애들
    }
    ans = abs(100 - N);
    for (int i = 0; i <= 1000000; ++i)
    {
        int len = check(i);
        if (len)
            ans = min(abs(N - i) + len, ans);
    }
    printf("%d", ans);
}
int check(int num)
{
    string s=to_string(num);
    int len = s.length();
    for (int i = 0; i < len; ++i)
    {
        if (X[s[i] - '0'])
            return 0;
    }
    return len;
}
cs

<풀이>

새롭게 재귀로 풀고나서 좀 늘었구나 싶었는데 

다른 사람들의 소스코드를 살펴보고나서 깨달음을 얻었다.

그냥 0번부터 100000번까지 for문으로 쫙 돌려보며 

가능한 숫자버튼으로 만들수 있는 채널이면 최솟값을 갱신시키는 방식이다.

코드가 80->60->40 줄로 짧아져서 기쁘긴한데 난 아직 멀었다.


저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 15686 치킨배달  (0) 2018.09.30
KOITP 고장난시계  (0) 2018.07.23
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22
백준 14888 연산자 끼워넣기 :: 들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
using namespace std;
int isVisited[9];
int N;
void dfs();
vector<int> v;
int main()
{
    scanf("%d", &N);
    dfs();
}
void dfs()
{
    if (v.size() == N)
    {
        for (int i = 0; i < v.size(); ++i)
            printf("%d ", v[i]);
        printf("\n");
    }
    for(int i=1;i<=N;++i)
        if (!isVisited[i])
        {
            isVisited[i] = 1;
            v.push_back(i);
            dfs();
            isVisited[i] = 0;
            v.pop_back();
        }
}
cs


<풀이>


visit를 확인하면서 방문 안한 숫자를 넣으며 재귀를 돈다.

depth를 들어가면서

visit를 체크해주고, 벡터의 맨끝에 새로 추가될 숫자를 넣어준다.

복귀하면서. visit 체크를 해제해주고 벡터의 맨 끝 숫자를 빼준다.

저작자표시

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

백준 10971 외판원 순회 2  (0) 2018.07.28
백준 10819 차이를 최대로  (0) 2018.07.27
KOITP 큰수만들기  (0) 2018.07.23
백준 11724 연결 요소의 개수 :: 들짐승  (0) 2018.07.23
백준 11403 경로 찾기 :: 들짐승  (0) 2018.07.23

<링크>

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

+ Recent posts

티스토리툴바