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


1. 문제 이해


 n(6 < n < 13)개 중에 6개를 뽑아 로또번호를 완성하는 것이 목표 입니다.

전형적인 완전 탐색 문제입니다.


2. 접근 방법


 dfs를 사용하여 문제를 해결해 보겠습니다. 

초기 깊이는 0부터 시작하며, 깊이가 6이 되었을때 방문했던 기록을 이용하여 6개의 숫자를 출력합니다.


탈출조건은 n개를 모두 탐색했을때로 두겠습니다.

인덱스 (0 ~ n-1) 에는 숫자가 들어 있고 n을 가르켰을때는 없으므로 루프 탈출!!

한가지 더!! 출력하는 것이 먼저!! 그 다음이 탈출 조건이 오도록 코드를 짜야 한다!!


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
#include <cstdio>
#include <string.h>
#define MAX_SIZE 14
using namespace std;
 
int n;
int lotto[MAX_SIZE];
bool visit[MAX_SIZE];
 
void dfs(int cur, int cnt) {
    if (cnt == 6) {
        for (int i = 0; i < n; i++) {
            if (visit[i]) printf("%d ", lotto[i]);
        }
        printf("\n");
    }
    if (cur == n) return;
 
    visit[cur] = 1;
    dfs(cur + 1, cnt + 1);
    visit[cur] = 0;
    dfs(cur + 1, cnt);
}
 
int main() {
 
    while (true) {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            scanf("%d", &lotto[i]);
        }
        memset(visit, false, sizeof(visit));
        dfs(0, 0);
        printf("\n");
    }    
 
    return 0;
}
cs



※ dfs로 문제를 접근할때 

  1) 깊이를 무엇으로 정할지,

  2) 탈출조건을 무엇으로 정할지 에 유의하며 문제를 하도록 해야겠다!

'Algorithm > solution' 카테고리의 다른 글

#1759. 암호 만들기  (0) 2017.12.29
#2140. 지뢰찾기  (0) 2017.12.29
#1463. 1로 만들기  (0) 2017.12.24
#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24

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


1. 문제 이해


n을 입력 받았을때 나누기3, 나누기2, 빼기1 3가지 연산을 사용하여 1로 만들때, 최소 연산수를 구하는 문제 입니다.


2. 접근 방법


다이나믹 프로그램으로 문제 해결을 해보겠습니다. 

이 표현이 맞는지는 모르겠으나, 작은문제에서 큰문제를 해결해 나가는 bottom-up 방식으로 문제를 해결했습니다.


3. 문제 해결


for문으로 완전 탐색을 하되, 크게 3가지로 분류했습니다.


1. 3의 배수인가?                                => 3곱해서 올 수 있고, 1 더해서 올 수 있다.

2. 2의 배수인가?                                => 2곱해서 올 수 있고, 1 더해서 올 수 있다.

3. 3의배수, 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
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 1000001
 
using namespace std;
 
int dp[MAX_SIZE];
 
int main() {
    int n;
    scanf("%d", &n);
 
    int res = 0;
    dp[1] = 0, dp[2] = 1, dp[3] = 1;
    for (int i = 4; i <= n; i++) {
        if (i % 3 == 0) {
            dp[i] = min(dp[i / 3], dp[i - 1]) + 1;
        }
        else if (i % 2 == 0) {
            dp[i] = min(dp[i / 2], dp[i - 1]) + 1;
        }
        else {
            dp[i] = dp[i - 1] + 1;
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}
cs


'Algorithm > solution' 카테고리의 다른 글

#2140. 지뢰찾기  (0) 2017.12.29
#6305. 로또  (0) 2017.12.26
#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23

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


1. 문제 이해


전형적인 탐색 문제입니다. 


2. 접근 방법


완전 탐색을 하되, 이분탐색으로 시간을 줄이도록 하겠습니다. 

저는 재귀로 이분탐색 함수를 작성할 것입니다.

재귀로 함수를 작성할때는 무한 루프에 빠지지 않게 탈출 조건을 먼저 만들도록 합니다!!


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
#include <algorithm>
#include <cstdio>
#define MAX_SIZE 500001
using namespace std;
 
int n, m;
int my[MAX_SIZE];
int chk[MAX_SIZE];
 
bool bs(int l, int r, int find) {
    int mid = (l + r) / 2;
 
    if (l > r) {
        return false;
    }
    else {
        if (my[mid] == find) return true;
        else if (my[mid] > find) return bs(l, mid - 1, find);
        else return bs(mid + 1, r, find);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &my[i]);
    }
    sort(my, my + n);
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &chk[i]);
    }
 
    for (int i = 0; i < m; i++) {
        int left = 0, right = n - 1;
        
        if (bs(0, n - 1, chk[i])) {
            printf("1 ");
        }
        else {
            printf("0 ");
        }
    }
    printf("\n");
    return 0;
}
cs


※ 항상 void로 함수를 작성하던 버릇에서 벗어나 좀더 세련되게 짜보았다.

※ cin, cout 보다는 scanf, printf가 빠르다!!

'Algorithm > solution' 카테고리의 다른 글

#6305. 로또  (0) 2017.12.26
#1463. 1로 만들기  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23
#11866. 조세퍼스 문제  (0) 2017.12.01

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


1. 문제 이해


각 자리 수가 등차 수열이 된다면 그 수는 한수 입니다.




2. 접근방법


for문을 이용한 완전탐색을 이용하여 한수를 찾아 보겠습니다.


저는 이 문제의 포인트를 자릿수로 정했습니다.

문제의 조건이 1000이하의 자연수 이므로 1자리에서 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
#include <iostream>
 
using namespace std;
 
int n, res;
 
void hansu_cnt(int cur) {
    if (cur / 100 - (cur / 10) % 10 == (cur / 10) % 10 - cur % 10) {
        res++;
    }
}
 
int main() {
    cin >> n;
 
    if (n > 99) {
        res = 99;
        for (int i = 100; i <= n; i++) {
            hansu_cnt(i);
        }
    }
    else {
        res = n;
    }
    cout << res << '\n';
}
cs


'Algorithm > solution' 카테고리의 다른 글

#1463. 1로 만들기  (0) 2017.12.24
#10815. 숫자카드  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23
#11866. 조세퍼스 문제  (0) 2017.12.01
#10828. 스택  (0) 2017.11.29

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

1. 문제 이해

 저 같은 경우는 문제 이해에서 완벽하게 넘어가지 않아 꽤나 고생했던 문제입니다.

함정 point는 n개의 똑같은 랜선을 만들어야 하는데 n보다 큰 경우인 n+1, n+2 경우에도 최대값을 체크해 줘야 한다는 것 입니다.


2. 접근방법

두가지 부분에서 조심해야 합니다.


첫 번째, 시간초과에 주의해야 합니다. 

완전탐색을 할 경우,  시간이 초과하기 때문에 binary search를 사용해야 합니다.


두 번째, 범위초과에 주의해야 합니다.

int 형으로 선언할 경우, 범위가 초과하는 경우(예를 들어, left(2^31-1 / 2)+right(2^31) / 2 = mid(int형 초과), 잘린 갯수(1로 잘랐을대 int형 초과))가 발생할 수 있기 때문에 long long형을 사용하도록 합니다.


세 번째,

저 같은 경우는 속도를 올리기 위해서 

'가장 작은 값을 기준으로 0부터 가장 작은 값 까지 이분탐색을 하자!' 로 접근하였습니다.

하지만 이렇게 접근한 경우, 밑의 test case 에서는 0이 출력 되버립니다. 즉, 완전 탐색이 할 필요가 있다는 것입니다.

4 5

100

200

302

400

그래서 최대값을 찾아 접근하여야 합니다. 최대값으로 설정할경우에도 이분탐색으로 탐색하기 때문에 O(logN) 이 되므로 시간 초과에 대해서 걱정 하지 않아도 됩니다.

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 <cstdio>
#define MAX_SIZE 10005
 
using namespace std;
 
int k, n;
long long res;
int arr[MAX_SIZE];
 
long long calc_lens(long long len) {
    long long output = 0;
    for (int i = 0; i < k; i++) {
        output += (arr[i] / len);
    }
    return output;
}
 
int main() {
    scanf("%d %d", &k, &n);
 
    long long _max = 0;
    for (int i = 0; i < k; i++) {
        scanf("%d", &arr[i]);
        _max = _max < arr[i] ? arr[i] : _max;
    }
 
    long long l = 1, r = _max;
    while (l <= r) {
        long long mid = (l + r) / 2;
        long long tmp = calc_lens(mid);
 
        if (tmp < n) {            // 크게 잘른것, 자르는 크기 줄여주기
            r = mid - 1;
        }
        else {                    // 크거나 같은경우
            res = res < mid ? mid : res;
            l = mid + 1;
        }
    }
 
    printf("%lld\n", res);
    return 0;
}
cs



※ long long 형은 9byte로 int(4byte)보다 더 많은 수를 표현할 수 있다.

※ MAX_SIZE 실수를 자꾸 한다.... 시간 초과가 날 경우 용량을 잘 확인하자!!!

'Algorithm > solution' 카테고리의 다른 글

#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#11866. 조세퍼스 문제  (0) 2017.12.01
#10828. 스택  (0) 2017.11.29
#1874. 스택수열  (1) 2017.11.29

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


1. 문제 이해

 둥글게 앉은 n명의 사람을 m번씩 건너 뛴 후에 뽑아내 그 순서를 나열하는 문제입니다. 

2. 접근방법

 문제를 보고 순환큐를 사용하겠다고 마음먹었습니다. 큐의 성질을 잘 이해하고 있다면, 쉽게 풀 수 있는 문제!!

3. 문제 해결

전체적인 루틴을 설명 드리겠습니다.

 우선, while 반복문을 실행 합니다. 

이 루프를 빠져 나오는 조건!! 큐에 아무것이 없을때 이 루프를 빠져 나오게 하려 합니다. 저는 여기서 "front == rear" 이 조건을 이용해서 이 루프를 빠져 나오겠습니다.


다음으로, 규칙을 잘 보시면 m-1번을 건너 뛴 이후에 m번째 사람이 뽑히게 되는것을 확인할 수 있게됩니다. 저는 m-1번을, 즉, 건너뛰는 사람들을 rear 뒤로 보낼 것 입니다. 그 다음으로 m번째 사람을 뽑고 그 값을 기록합니다.


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
#include <stdio.h>
#define MAX 1000000
 
int qu[MAX];
int output[MAX];
int front =-1;
int rear =-1;
 
void push(int n) {
    qu[++rear] = n;
}
 
int pop() {
    if (front == rear) {
        return -1;
    }
    else {
        return qu[++front];
    }
}
 
int main() {
    int n, m;
    int i, cnt=0;
 
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; i++) {
        push(i);
    }
 
    while (front != rear) {
        for (i = 0; i < m - 1; i++) {
            push(pop());
        }
        output[cnt] = pop();
        cnt++;
    }
 
    printf("<");
    for (i = 0; i < n - 1; i++) {
        printf("%d, ", output[i]);
    }
    printf("%d>\n", output[i]);
}
 


cs



※ 느낀점.

이 문제를 풀게 됨으로써 큐라는 자료구조를 이해할 수 있었습니다. 


'Algorithm > solution' 카테고리의 다른 글

#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23
#10828. 스택  (0) 2017.11.29
#1874. 스택수열  (1) 2017.11.29

#10828. 스택


1. 문제 이해


 스택에 pop, push 등 기본적인 기능을 이해하고 해결 하는 문제 입니다.


2. 접근 방법


 stack의 push와 pop에 대한 이해를 바탕으로 문제를 해결해 나가도록 하겠습니다.


3. 문제 해결


1단계와 2단계로 나누어서 문제를 해결 나가기로 하겠습니다.


[1단계]


 문제에서 주어진 함수기능 구현합니다.


[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
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include<string.h>
#define MAX 10000
 
typedef struct Stack {
    int s[MAX];
    int top;
}Stack;
 
Stack stack;
 
void push(int x) {
    if (stack.top == MAX - 1) {
 
    }
    else {
        stack.s[++stack.top] = x;
    }
}
 
int pop() {
    if (stack.top == -1) {
        return -1;
    }
    else {
        stack.top -= 1;
        return stack.s[stack.top+1];
    }
}
 
int size() {
    return stack.top + 1;
}
 
int empty() {
    if (stack.top == -1) {
        return 1;
    }
    else {
        return 0;
    }
}
 
int top() {
    if (stack.top == -1) {
        return -1;
    }
    else {
        return stack.s[stack.top];
    }
}
 
int main() {
    int num;
    int pnum;
    int i;
    char c[20];
    stack.top = -1;
    scanf("%d", &num);
 
 
    for (i = 0; i < num; i++) {
        scanf("%s", c);
        if (!strcmp(c, "push")) {
            scanf("%d", &pnum);
            push(pnum);
        }
        else if (!strcmp(c, "pop")) {
            printf("%d\n", pop());
        }
        else if (!strcmp(c, "size")) {
            printf("%d\n", size());
        }
        else if (!strcmp(c, "empty")) {
            printf("%d\n", empty());
        }
        else {
            printf("%d\n", top());
        }
    }
 
    return 0;
}
cs


※ 느낀점

1. strcmp(a, b) 

  - a의 유니코드가 b의 유니코드보다 더 크면 양수.

  - a의 유니코드가 b의 유니코드보다 더 작으면 음수.      => 즉, 두 값이 다르면 +,-

  - 같으면 0


tip)) c는 0이 아닌수는 true, 0이면 false 입니다.

'Algorithm > solution' 카테고리의 다른 글

#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23
#11866. 조세퍼스 문제  (0) 2017.12.01
#1874. 스택수열  (1) 2017.11.29

#1874. 스택수열


1. 문제 이해


 우선, 제목에서 보이듯이 스택을 사용하여 해결하는 문제인걸로 보입니다. test case로 입력을 '4 3 6 8 7 5 2 1'을 받았을때, 이 수열을 1부터 n까지 오름차순으로 들어오는 수로 만든 stack으로 만들 수 있다면 push, pop 과정을 나열하거나, 수열이 만들어 지지 않는 다면 NO를 출력하는 문제입니다.


2. 접근방법


 저는 1단계와 2단계로 나누어서 진행을 해보았습니다.


1단계, no 단계를 생각하지 않고, 어떻게 push(+)와 pop(-)을 출력해 나갈지에 대한 루틴 고민하기.


2단계, NO로 가는 경로 찾기.



3. 문제 해결


[1단계]


 test case : [4 3 6 8 7 5 2 1]를 이용하여 루틴을 찾아 보도록 하겠습니다.

맨 처음으로 4를 입력 받게 된다면, 우리는 1부터 4까지 push를 할 수 밖에 없습니다. 즉, 입력받는 새로운 값이 증가할때 마다 결국엔 push할 수 밖에 없다는 것 입니다.

 자, 여기서 힌트를 얻어 MAX라는 기준을 만들어 새로 입력받는 값이 MAX보다 크다면, 이전 MAX부터 다음 MAX만큼 push가 일어나는 루틴을 찾을 수 있습니다.

 반대로, MAX보다 작다면 현재 스택에 top의 위치를 확인합니다. 스택에 경우, top이 가리키는 값이 pop 될 수 밖에 없기 때문에 top이 가리키는 값이 test case 다음값과 같다면 pop을 수행해 줍니다.


[2단계]

 

 이제 NO의 경우를 찾아 보도록 하겠습니다. 이 문제의 경우에는 1단계에서 조금만 더 생각해 본다면 쉽게 solution을 찾을 수 있습니다. 

 MAX보다 작다면 현재 top의 위치를 확인하여 그 값이 test case 다음값과 같다면 pop을 수행했습니다. 이 부분을 상기 한다면, 반대로 test case 값과 같지 않을때는 NO가 나오는것을 생각해 낼 수 있습니다.


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
#include <stdio.h>
#define MAX 100000
#define S_MAX 200000
 
typedef struct Stack {
    int s[S_MAX];
    int top;
}Stack;
 
Stack stack;
 
int main() {
    int num;
    int input[MAX];
    char output[S_MAX];
    int i, j;
    stack.top = -1;
    int cnt = 0;
    int output_i = 0;
    int max = 0;
 
    scanf("%d", &num);
 
    for (i = 0; i < num; i++) {
        scanf("%d", &input[i]);
        if (max < input[i]) {
            for (j = max; j < input[i]; j++) {
                max = input[i];
                
                stack.s[++stack.top] = (++cnt);
                output[output_i++] = '+';
            }
            --stack.top;
            output[output_i++] = '-';
        }
        else if (max > input[i]) {
            if (stack.s[stack.top] != input[i]) {
                printf("NO");
                return;
            }
            else if (stack.s[stack.top] == input[i]) {
                --stack.top;
                output[output_i++] = '-';
            }
        }
    }
    for (i = 0; i < output_i; i++) {
        printf("%c\n", output[i]);
    }
}
cs



※ 느낀점 

1. 기능(function)에 printf는 절대 넣지 말자.

2. 문자열을 출력 하는 방법 2가지.

  - %s : 'n\'(null)을 만날때까지 출력. 

  - %c : for문 사용 (여기선 null이 없기 때문에)

3. 출력은 입력의 2배가 된다. (이 문제의 경우에서만!)



'Algorithm > solution' 카테고리의 다른 글

#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23
#11866. 조세퍼스 문제  (0) 2017.12.01
#10828. 스택  (0) 2017.11.29

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
#include<stdio.h>
#define MAX 10000
 
/* 스택
top 은 -1로 초기화.
*/
typedef struct Stack {
    char memory[MAX];
    int top;
}Stack;
 
Stack stack;
 
int empty() {        
    if (stack.top == -1) {
        return 1;        
    }
    else {
        return 0;        
    }
}
 
int full() {
    if (stack.top == MAX-1) {
        return 1;
    }
    else {
        return 0;
    }
}
 
void push(char c) {
    if (full()) {
        printf("full");
    }else {
        stack.memory[++stack.top] = c;
    }
}
 
void pop() {
    if (empty) {
        printf("empty");
    }
    else {
        stack.top -= 1;
    }
}
 cs


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
#include <stdio.h>
#define MAX 1000
 
/* 원형 큐
원형큐는 공간 하나를 비워 둔다. why)) 원형 큐가 비어있는지 알수있게 하기 위해서!!
full : rear +1 == front
empty : rear == front
*/
 
 
typedef struct CirQueue {
    int q[MAX];
    int front;
    int rear;
};
 
struct CirQueue cq;
 
void cir_push(int n) {
if ( cq.rear + 1== cq.front) {
        printf("full");
    }
    else {
        cq.q[(cq.rear + 1)%MAX] = n;
    }
}
 
int cir_pop(){
    if (cq.front == cq.rear) {
        printf("empty");
    }
    cq.q[(cq.front+1)%MAX];
    return cq.q[cq.front];
}
/* normal queue 
front, rear = 0 (초기화)
    => 단점: 공간이 낭비 됨
    => solution)) 원형 큐!!
*/
struct CirQueue qu;
 
void push(int n) {
    if (qu.rear == MAX -1) {
        printf("full");
    }
    else {
        qu.q[++qu.rear] = n;
    }
}
 
void pop() {
    if (qu.front == qu.rear) {
        printf("empty");
    }
    else {
        qu.front += 1;
    }
}
 cs


---------------------------------------------------------------------------------------------

오늘의 문제 : 10828번(스택), 1874번(스택수열)


(+)추가문제 : 1918번(후위연산자)

---------------------------------------------------------------------------------------------


시작이 반이다!! 라는 시작으로 열심히 시작해 보겠습니다!! silverbell 화이팅!!

+ Recent posts

티스토리툴바