https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4su3xKXFUDFAUf


1. init()이 한번만 실행될 수 있게 flag를 넣었다.

2. A->B B->A가 같음을 이용하여 query 수를 줄였다. 대신 compare()와 visit배열을 이용해 답을 찾아갔다.


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
88
89
90
91
92
93
94
95
96
#if 0
#define N          4
 
typedef struct {
    int strike;
    int ball;
} Result;
 
// API
extern Result query(int guess[]);
 
Result compare(int key, int obj)
{
    int count[10] = { 0 };
    Result result = { 0, 0 };
    
    for (int i = 0; i < N; ++i){
        ++count[key % 10];
        ++count[obj % 10];
        if (key % 10 == obj % 10) ++result.strike;
        key = key / 10;
        obj = obj / 10;
    }
 
    for (int i = 0; i < 10; ++i){
        if (count[i] == 2) ++result.ball;
    }
 
    result.ball -= result.strike;
 
    return result;
}
 
int A[6000];
int V[10000];
int Count_guess;
int flag_init = 0;
 
void init(void)
{
    int i, j, k, l;
    
    if (flag_init == 0){
        flag_init = 1;
        Count_guess = 0;
        for (i = 0; i < 10; ++i){
            for (j = 0; j < 10; ++j){
                if (j == i) continue;
                for (k = 0; k < 10; ++k){
                    if (k == i || k == j) continue;
                    for (l = 0; l < 10; ++l){
                        if (l == i || l == j || l == k) continue;
                        A[Count_guess++] = 1000 * i + 100 * j + 10 * k + l;
                    }
                }
            }
        }
    }
 
    for (register int i = 0; i < Count_guess; ++i) V[A[i]] = 0;
}
 
void doUserImplementation(int guess[]) 
{
    Result result;
    Result hub;
    int key;    
 
    init();
 
    while (1){
        for (register int i = 0; i < Count_guess; ++i){
            if (V[A[i]] == 0) {
                key = A[i];
                guess[3] = A[i] % 10;
                guess[2] = (A[i] / 10) % 10;
                guess[1] = (A[i] / 100) % 10;
                guess[0] = A[i] / 1000;
                result = query(guess);
                break;
            }
        }
 
        if (result.strike == 4) break;
 
        for (register int i = 0; i < Count_guess; ++i){
            if (V[A[i]] == 0){
                hub = compare(key, A[i]);
                if (hub.ball == result.ball && hub.strike == result.strike) continue;
                V[A[i]] = 1;
            }
        }
    }
}
 
#endif
cs


저작자표시 (새창열림)

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

1244 최대 상금  (0) 2018.09.20
1210 Ladder1  (0) 2018.09.20
1204 최빈수 구하기  (0) 2018.09.20
1206 View  (0) 2018.09.18
1251 하나로  (0) 2018.09.18

하노이 탑 막대기 4개일 때 생각해봄.

값이 일정하게 나오는 것으로 봐서 더 일반적으로 생각할 수 있겠는데 일단 DP로 짜봤다.


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
//하노이의 탑 4개
#if 1
#include <iostream>
 
#define    INF    (0x7fffffff)
#define MAX_DISK    (50+1)
 
long long T[MAX_DISK];
 
#define MIN(x, y)    ((x)<(y)?(x):(y))
long long DP(int N)
{
    if (N == 0) return 0;
    if (T[N] != 0) return T[N];
 
    long long ans = INF;
    for (register int i = 1; i <= N - 1; ++i){
        ans = MIN(ans, 2 * T[i] + (1ll << (N - i)) - 1);
    }
    return T[N] = ans;
}
 
int main(void)
{
    T[0] = 0;
    T[1] = 1;
    for (int i = 1; i <= 100; i++){
        printf("#%d %lld, 차이: %lld\n", i, DP(i), DP(i) - DP(i - 1));
    }
    return 0;
}
#endif
cs


저작자표시 (새창열림)
https://www.acmicpc.net/problem/11279

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
//BOJ_11279 최대 힙
#if 01
#pragma warning(disable:4996)
#include <iostream>
 
#define MAX    (100001)
 
int N;
int Heap[MAX];
int HP;
 
#define SWAP(x,y)    {int temp; temp=x; x=y; y=temp;}
void PushHeap(int x)
{
    Heap[++HP] = x;    //마지막 위치에 삽입
    for (int i = HP; i > 1; i /= 2) {
        if (Heap[i / 2] < Heap[i]) SWAP(Heap[i / 2], Heap[i])
        else break;
    }
}
 
int PopHeap(void)
{
    int ans = Heap[1];
    Heap[1] = Heap[HP];
    Heap[HP--] = 0;
 
    for (int i = 1; i * 2 <= HP;)
    {
        if (Heap[i] > Heap[i * 2] && Heap[i] > Heap[i * 2 + 1]) break;
        else if (Heap[i * 2] > Heap[i * 2 + 1])
        {
            SWAP(Heap[i], Heap[2 * i]);
            i = 2 * i;
        }
        else
        {
            SWAP(Heap[i], Heap[2 * i + 1]);
            i = 2 * i + 1;
        }
    }
    return ans;
}
 
int main(void)
{
    int hub;
 
    scanf("%d", &N);
    for (register int i = 0; i < N; ++i){
        scanf("%d", &hub);
        if (hub == 0) {
            if (HP == 0) printf("0\n");
            else printf("%d\n", PopHeap());
        }
        else PushHeap(hub);
    }
    return 0;
}
 
#endif
cs


저작자표시 (새창열림)

+ Recent posts

티스토리툴바