문제에서 double을 다뤄야 하면, 주의해야할 점들이 있어서 나열해 본다.

 

이 문제를 보자.

먼저, double을 int로 변환해야하는 경우 단순한 형변환으로는 부족할 수 있다.

예를 들어 다음코드를 돌려보면 1004가 아닌 1003이 찍힌다.

1
2
3
4
5
6
7
int32_t main()
{
    double a = 10.04 * 100;
    int b = a;
    printf("%d\n", b);
    return 0;
}
cs

이경우 다음처럼 뒤에 0.5를 곱해주고 변환해야 제대로 변환된다.

1
2
3
4
5
6
7
int32_t main()
{
    double a = 10.04 * 100 + 0.5;
    int b = a;
    printf("%d\n", b);
    return 0;
}
cs

 

아래처럼 rint를 쓰면 가까운 int로 변환해서 해당문제가 없어진다고 한다.

double a = 10.04 * 100;
int b = (int) rint(a);
printf("%d\n", b);

 

 

반응형

'Programming > Problem Solving' 카테고리의 다른 글

백준 4103 ATM  (0) 2020.05.05
백준 15481 그래프와 MST  (0) 2020.05.02
BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05

문제링크는 여기


풀이과정

출발점은 하나로 정해져 있고, 도착점은 여러개.

현금인출은 사이클 도는게 유리하므로 SCC단위로 생각하면 됨.

도착점도 SCC단위로 묶어서 생각하면 됨.

SCC단위로 묶고나서 보면, 간선 가중치는 없는 방향그래프 이므로, 위상정렬 개념 도입해서 longest 구하면 답

(여기서 위상정렬이 아닌 단순 BFS로는 안풀린다. 그래프 최장거리 참조)


헷갈렸던 점

아래 그래프가 SCC이후에 만들어진 DAG이라고 해보자. 

1번정점이 시작, 5번 정점이 끝이라고 해보자.


위의 그래프를 아래와 같은 코드로 위상정렬하면서 돌리게 되면

1
2
3
4
5
6
7
8
9
10
enqueue({ start_v, cost[start_v] });
while (q.size()) {
    auto n = q.front(); q.pop();
    max_dist[n.v] = max(max_dist[n.v], n.w);
    for (auto adj : adj_list[n.v]) {
        max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj]=1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}
cs


1번노드를 처리한다음에 2번 노드처리하기전에 while()이 끝나게 된다. (2번 노드의 in_edge가 3이라서 1빼도 아직 2라서 3과 4를 처리하기 전까진 못들어가는데 3,4를 처리하지 않는 코드이다.)

하지만 정답은 1 -> 2 -> 3을 모두 계산한 최대비용이 답이었던것.. 


따라서, 아래처럼 처음에 indegree가 0인 모든 정점을 queue에 넣어주고, cal[v] 맵을 사용해서 유효한 경우에만 max_dist가 갱신되도록 해주면 OK

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
if (start_v == -1for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
else max_dist[start_v] = cost[start_v];
vi cal(max_v + base1); cal[start_v] = 1;
while (q.size()) {
    auto n = q.front(); q.pop();
    for (auto adj : adj_list[n.v]) {
        if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}
cs



코드

scc_dag_kosaraju()를 라이브러리화 하고, 기존 longest()라이브러리를 활용하느라고, 범용성 관점에서 코드가 좀 길고 장황한면이 있습니다. 감안해서 봐주세요~

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*{{{*/
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "dbg.h"  // https://github.com/sharkdp/dbg-macro
#define FileInput freopen("input.txt""rt", stdin)
#else
#define dbg(...)
#define FileInput
#endif
//#define int long long
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define CASE_T int ___T; cin>>___T;for(int cs=1;cs<=___T;cs++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
#define endl '\n';
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define IN(n) int n;cin>>n
#define IN2(a,b) int a,b;cin>>a>>b
#define OUT(x) cout << (x) << endl
template <class T>
void OUTV(vector<T>& v) { REP(i, SZ(v)) cout << v[i] << (i + 1 == SZ(v) ? '\n' : ' '); }
typedef long long ll;
const int INF = (int)1e9;
/*}}}*/
 
struct result { vvi scc_list; vvi scc_adj_list; vi scc_cost; int scc_start_v; vi scc_end_v; };
result scc_dag_kosaraju(int max_v, int start_v, vi& end_v, vvi& adj_list, vvi& adj_rlist, vi& cost, int base1)
{
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(max_v + base1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (int a : adj_list[n]) dfs(a);
        S.push(n);
    };
    for (int i = base1; i < max_v + base1; i++if (visit[i] == 0) dfs(i);
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(max_v + base1);
    vi scc(max_v + base1);  // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것
    int scc_ix = base1;
    vvi scc_list; if (base1) scc_list.push_back(vi());
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi sl;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            scc[n] = scc_ix;
            sl.push_back(n);
            for (auto a : adj_rlist[n]) dfs(a);
        };
        dfs(n);
        scc_list.push_back(sl);
        scc_ix++;
    }
    vvi scc_adj_list(scc_ix); int scc_start_v = -1; vi scc_end_v(scc_ix), scc_cost(scc_ix);
    for (int u = base1; u < max_v + base1; u++) {
        if (u == start_v) scc_start_v = scc[u];
        if (end_v[u]) scc_end_v[scc[u]] = 1;
        scc_cost[scc[u]] += cost[u];
        for (auto v : adj_list[u]) {
            if (scc[u] != scc[v]) {
                //cout << scc[u] << ' ' << scc[v] << endl;
                scc_adj_list[scc[u]].push_back(scc[v]);
            }
        }
    }
    return { scc_list, scc_adj_list, scc_cost, scc_start_v, scc_end_v };
}
struct node { int v, w; };
using vvn = vector<vector<node>>;
struct result2 { vi max_dist; int max_value; vi path; };
result2 longest(int max_v, int start_v, vvi& adj_list, vi& in_edge, vi& cost, vi& end_v, int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF);
    vi from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0return false;
        q.push(n);
        return true;
    };
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    if (start_v == -1for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
    else max_dist[start_v] = cost[start_v];
    vi cal(max_v + base1); cal[start_v] = 1;
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
            in_edge[adj]--;
            if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
        }
    }
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (end_v[i] && max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    FileInput;
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1), adj_list2(V + 1);
    REP(i, E) {
        int a, b; cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list2[b].push_back(a); // 역방향
    }
    vi cost(V + 1);
    REP1(i, V)cin >> cost[i];
    IN2(S, P);
    vi end_v(V + 1);
    REP(i, P) { IN(p); end_v[p] = 1; }
    auto r = scc_dag_kosaraju(V, S, end_v, adj_list, adj_list2, cost, true);
    int N = SZ(r.scc_adj_list) - 1;
    vi in_edge(N + 1);
    REP1(u, N) for (auto v : r.scc_adj_list[u])in_edge[v]++;
    auto r2 = longest(N, r.scc_start_v, r.scc_adj_list, in_edge, r.scc_cost, r.scc_end_v, true);
    OUT(r2.max_value);
    return 0;
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

double과 관련된 핸들링  (0) 2021.12.26
백준 15481 그래프와 MST  (0) 2020.05.02
BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05

문제는 여기


특정간선을 포함하는경우, 실제 MST보다 큰 값이 나올 수 있다. (프루스칼로 MST를 구할때는 간선을 정렬한다음에 최소간선부터 시작함을 상기하자)

MST 한 번 하는데 $O(E \times log E)$ 니까, 간선개수만큼 하면 $O(E^2 \times log E)$ 일거고.. E가 10^5보다 크므로 나이브하게 해서는 TLE확정이다.


풀이방법

MST를 구한다음에.. 해당 간선이 이미 포함돼 있으면 MST값을 그냥 찍으면 되고, 만약 포함되어 있지 않으면 포함시키고, 다른 간선중 하나를 빼는식으로 하면 된다.

잘 이해가 가지 않는다면 다음 그래프를 보자. (간선 가중치는 생략돼 있지만 MST를 그린 화면으로 생각하자)

여기서 만약 정점 1과 정점4를 잇는 간선을 포함한 답을 구한다고 생각해보자. (위그림에서는 정점1과 정점4 사이에 간선이 없지만 원래는 있었는데 MST구하면서 제거됐다고 가정)

위 그림에서 알 수 있듯이 MST에 (1,4)간선을 추가한 순간 사이클이 생기기 때문에, (1,6) (6,2) (2,5) (5,3) (3,4) 중 하나를 대신 끊어줘야 한다.

이때 나이브하게 경로를 쭉 따라가면서 가중치 가장 큰 걸 빼주는 식으로 하면, 그래프 구조가 직선적인 경우 O(E)가 걸리게 되어 E개의 쿼리를 처리하는데 O(E^2)이 걸려서 TLE가 나게된다.

따라서 위에 LCA로 표시했지만 공통조상까지 올라가고, 내려오는 경로상에서 스파스 테이블을 사용해서 효율적으로 최대가중치를 가진간선을 골라줘야 한다. 참고로 LCA에서 최대가중치 간선을 고르는 문제는 여기에 있다.


코드

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;
const int INF = (int)1e9;
const int MAXN = 200001;
const int LOG_N = 19;
 
struct node3
{
    int u, v, w;
    bool operator < (const node3& t) const {
        return w < t.w;
    }
};
struct node2 { int v, w; };
bool operator<(node2 l, node2 r) { return l.w > r.w; }
vector<vector<node2>> adj_list(MAXN);
 
ll MST_Kruskal(int max_v, vector<node3> v) {
    struct union_find {
        vector<int> parent;
        union_find(int n) {
            parent.resize(n + 1);
            for (int i = 0; i <= n; i++) parent[i] = i;
        }
        int find(int v) {
            return v == parent[v] ? v : parent[v] = find(parent[v]);
        }
        bool uni(int u, int v) {
            u = find(u), v = find(v);
            if (u == v) return 0;
            parent[u] = v;
            return 1;
        }
    };
    union_find uf(max_v);
    sort(v.begin(), v.end());
    ll ans = 0;
    for (auto a : v) {
        if (uf.uni(a.u, a.v)) {
            adj_list[a.u].push_back({ a.v,a.w });
            adj_list[a.v].push_back({ a.u,a.w });
            ans += a.w;
        }
    }
    return ans;
}
 
 
//무방향그래프를 인풋으로 받아, 트리로 만들어준다.LCA를 위한 작업도 해준다.
struct result { int root; int max_level; };
vi parent(MAXN), level(MAXN), dist2(MAXN);
// ancestor[y][x] :: x의 2^y번째 조상을 의미
vvi ancestor(LOG_N + 1, vi(MAXN, -INF));  
 
result treefy(vector<vector<node2>>& adj_list, int root=-1,bool base1=false) {
    int max_v = (int)adj_list.size();
    int max_level = LOG_N;
    function<void(node2, intint)> dfs = [&](node2 n, int par, int lv) {
        parent[n.v] = par, level[n.v] = lv, dist2[n.v] = n.w;
        ancestor[0][n.v] = par;  // 첫번째(2^0) 조상은 부모
        for (auto adj : adj_list[n.v]) {
            if (adj.v == par) continue;  // 부모방향 간선제거
            dfs(adj, n.v, lv + 1);
        }
    };
    dfs({ root,0 }, -INF, 1);
    for (int i = 1; i <= max_level; i++) {
        for (int j = 1; j < max_v; j++) {
            int tmp = ancestor[i - 1][j];
            if (tmp == -INF) continue;
            ancestor[i][j] = ancestor[i - 1][tmp];
        }
    }
 
    return { root, max_level };
}
 
int lca(int u, int v, vi& level, vvi& ancestor)
{
    if (level[u] < level[v]) swap(u, v);  // b가 더 깊도록 조정
 
    int diff = level[u] - level[v];
    for (int i = 0; diff; i++) {
        if (diff & 1) u = ancestor[i][u];  //b를 올려서 level을 맞춘다.
        diff >>= 1;
    }
    if (u == v) return u;
    for (int i = LOG_N; i >= 0; i--) {
        // a와 b가 다르다면 현재 깊이가 같으니, 깊이를 a,b동시에 계속 올려준다.
        if (ancestor[i][u] != ancestor[i][v]) 
            u = ancestor[i][u], v = ancestor[i][v];
    }
    return ancestor[0][u];
 
 
}
 
int N, M, u, v, w;
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); 
    cin >> N >> M;
    vector<node3> vv;
    for(int i=0;i<M;i++) {
        cin >> u >> v >> w;
        vv.push_back({ u,v,w });
    }
    auto mst = MST_Kruskal(N, vv);
 
    result r = treefy(adj_list, 1true);
    vector<vector<int>> max_dp(r.max_level + 1vector<int>(N + 10));
    for (int i = 1; i <= N; i++) max_dp[0][i] = dist2[i];
    for (int jump = 1; jump <= r.max_level; jump++)
    {
        for (int here = 1; here <= N; here++)
        {
            int tmp = ancestor[jump - 1][here];
            if (tmp == -INF) continue;
            max_dp[jump][here] = 
                max(max_dp[jump - 1][here], max_dp[jump - 1][tmp]);
        }
    }
 
    for(int i=0;i<M;i++)
    {
        auto [s, e, w] = vv[i];
        int l = lca(s, e, level, ancestor);
 
        int mx = -1;
        int diff = level[s] - level[l];
        for (int j = 0; diff; j++) {
            if (diff & 1) mx = max(mx, max_dp[j][s]), s = ancestor[j][s];
            diff >>= 1;
        }
        diff = level[e] - level[l];
        for (int j = 0; diff; j++) {
            if (diff & 1) mx = max(mx, max_dp[j][e]), e = ancestor[j][e];
            diff >>= 1;
        }
 
        cout << mst + w - mx << '\n';
    }
 
    return 0;
}
cs










반응형

'Programming > Problem Solving' 카테고리의 다른 글

double과 관련된 핸들링  (0) 2021.12.26
백준 4103 ATM  (0) 2020.05.05
BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05



Binary Search Tree 구현을 해보았다. 

트리 만드는 부분 까지만 되어 있다.

지금은 root부터 insert로 트리를 생성하게 되어 있는데, 첨에는 다르게 해보다가 엄청 고생함.

최적화 된 형태는 아니기 때문에 향후에 업데이트 될 가능성은 크다.

인접리스트로만 구현하려고도 해봤는데, left, right가 [0], [1]로 되어야 해서 좀 어색하고,

특히 parent처리하려면 별도 배열을 쓰거나 node안에 w옆에 넣어야 하는데 좀 어색함

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 <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct node { int parent, l, r; };
int root, c, n, u, v;
#define MAX_NODE (1000001)
 
void insert(vector<node>& tree, int n, int v) {
    if (v < n) {
        if (tree[n].l == 0) { tree[n].l = v, tree[v].parent = n; return; }
        insert(tree, tree[n].l, v);
    }
    else {
        if (tree[n].r == 0) { tree[n].r = v, tree[v].parent = n; return; }
        insert(tree, tree[n].r, v);
    }
}
int main()
{
    vector<node> tree(MAX_NODE);
    cin >> root;
    tree[root] = { -1,0,0 };
    while (cin >> n) {
        insert(tree, root, n);
    }
    return 0;
}
 
cs


이걸로 post_order로 순회하는 것까지 구현한게 아래 코드이고, 이 문제에 대한 답안이기도 하다.

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
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct node {int parent,l,r;};
int root,c,n,u,v;
vector<node> tree(1000001);
 
void post_order(int n){
    if(n==0return;
    post_order(tree[n].l);
    post_order(tree[n].r);
    cout << n << '\n';
}
void insert(int n, int v){
    if(v<n){
        if(tree[n].l==0) {tree[n].l=v,tree[v].parent=n;return;}
        insert(tree[n].l,v);
    } else{
        if(tree[n].r==0) {tree[n].r=v,tree[v].parent=n;return;}
        insert(tree[n].r,v);
    }
 
}
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt""rt", stdin);
#endif
    cin >> root;
    tree[root] = {-1,0,0};
    while(cin >> n){
        insert(root, n);
    }
    post_order(root);
    int sdf = 1;
    return 0;
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

백준 4103 ATM  (0) 2020.05.05
백준 15481 그래프와 MST  (0) 2020.05.02
인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
Visual Studio Code  (0) 2020.04.03

그래프 문제를 풀때 인접행렬, 인접리스트를 다룰일이 워낙 많아서 별도 글로 하나 정리해 둔다.


인접행렬보다는 인접리스트로 구현하는게 일반적으로 더 나은데, 간선수가 최대일 경우 정점의 개수 제곱정도 되는데 인접행렬로 구현하게 되면 항상 이정도 복잡도를 가지는 반면 인접리스트로 구현하면 간선이 드물수록 속도 업이 된다. (예를 들어 그래프가 트리인 경우 최대 간선수는 정점의 제곱이 아닌 정점의 개수-1개 정도로 줄어든다.)


그래서 인접리스트 구현을 먼저 실어두고 나중에 PS할때 이용하려고 한다.


인접리스트 간선가중치 없는 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
int N, M, u, v;
int32_t main()
{
    cin >> N >> M;
    vector<vector<int>> adj_list(N + 1);
    REP(i,M){
        cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    return 0;
}
cs


인접리스트 간선가중치 있는 경우

w=1로 놓으면 간선가중치 없는 경우에도 범용적으로 쓸수 있기는 한데.. 무거울듯?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
int main()
{
    //V:정점개수, E:간선개수
    int V, E; scanf("%d%d%d"&V, &E);
    vector<vector<node>> adj_list(V + 1);
    for (int i = 0; i < E; i++) {
        int u, v, w; scanf("%d%d%d"&u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    return 0;
}
 
 
cs



인접행렬 간선가중치 있는 경우

간선가중치 없는 경우는 단순하게 w대신 1을 넣어주면 되기 때문에 트리비얼하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 4;
int n, m, u, v, w;
int main()
{
    scanf("%d%d"&n, &m);
    vector<vector<int>> in(n+1vector<int>(n+1, INF));  // 없는간선은 INF
    // 위에가 좀 문법적으로 헤비하면 int in[1001][1001]; 이런식으로 써도 된다.초기화 별도
    for (int i = 0; i < n; i++) in[i][i] = 0;  // 자기자신은 0
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d"&u, &v, &w);
        // 간선이 여러개일경우, 최단거리 단선만 기억(인접리스트와 다르게 이처리 필수)
        // 이문제의 경우 1-base index라 1빼줌(문제에 따라 다르게 처리)
        in[u - 1][v - 1= min(in[u - 1][v - 1], w);
    }
    return 0;
}
 
cs



반응형

'Programming > Problem Solving' 카테고리의 다른 글

백준 15481 그래프와 MST  (0) 2020.05.02
BST 트리 구현  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
Visual Studio Code  (0) 2020.04.03
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02

just store Lunlun numbers in an array.좋은 문제를 발견하면, 그 문제의 뽕을 뽑아먹는(충분히 검토하는) 코뽕시간입니다 ㅎ


오늘의 코뽕문제는 AtCoder Beginner Contest 161 - D Lunlun Number가 되겠습니다.

이 문제는 설명이 단순하고 쉽기 때문에 나중에 다시 문제를 recall하기도 좋고 풀이도 다양해서 코뽕에 아주 적합한 문제가 되겠습니다.

참고로 이 Lunlun number는 OEIS에 등록되어 있습니다.


이문제는 대략 살펴보아도 


브루트포스, 백트래킹, 이진탐색, Queue 등을 이용해서 풀 수 있는걸로 보입니다.


브루트 포스를 이용한 방법

먼저 브루트포스를 이용한 방법은, 단순히 1씩 증가시키면서 lunlun 넘버인지 보는코드에다가 일정부분을 스킵할 수 있는 코드를 삽입하는 간단한 방법입니다. 샘플코드는 다음과 같습니다.

예들들어 현재 숫자가 243일때 2가 violation이므로 둘째자리 숫자인 4가 9가 될때까지 50을 더해서 293까지 skip한다는 idea. 

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
 
ll lun[100001];
int check_lunlun(ll i) {
    int a = -1;
    int jari = 1;
    while (i) {
        int ii = i % 10;
        if (a == -1) a = ii;
        else if (abs(a - ii) > 1) {
            if (a > ii && a < 9)
                return (jari / 10* (10 - a - 1);
            else return 1;
        }
        i /= 10; jari *= 10, a = ii;
    }
    return 0;
}
int main() {
    int K; scanf("%d"&K);
    int k = 1;
    for (ll i = 1; k <= K; i++) {
        ll skip = check_lunlun(i);
        if (skip == 0) lun[k++= i;
        else i += skip - 1;
    }
    printf("%lld\n", lun[K]);
    return 0;
}
cs

이정도 아이디어만 가지고도 AC를 받기에는 충분(대략 700ms정도 걸림)

다른 아이디어도 적용하면 좀 더 스킵할수도 있을것임


아래는 다른사람들 방법

just store Lunlun numbers in an array.

근데 이건 원리상 아래 BFS랑 동일한거 같다.


백트래킹을 이용한 방법

678이라는 임의의 Lunlun넘버를 생각해 봤을때, 다음처럼 3가지 경우로 갈 수 있다고 생각하고, DFS를 돌리는 아이디어.


이건 실전에서 구현하기도 좋아보인다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
map<ll, int> m;
void dfs(ll i) {
    m[i] = 1
    if (i > 3234566667ll) return;
    int ld = i % 10;
    if(ld+1<=9) dfs(i * 10 + ld + 1);
    dfs(i * 10 + ld);
    if(ld-1>=0)dfs(i * 10 + ld - 1);
}
int main()
{
    for (int i = 1; i < 10; i++) dfs(i);
    int k; cin >> k;
    int ix = 1;
    for (auto a : m) {
        if (ix++ == k) cout << a.first << endl;
    }
    return 0;
}
cs

특별히 백트래킹이랄것도 없고.. 그냥 최대숫자보다 커지면 return하는게 다인데.. 저 최대숫자를 모르면 좀 애매하다는게 문제라면 문제.. DFS특성상 11111111111111 이런숫자를 먼저 최대자리수까지 파는 경향이 있기 때문에 더욱그렇다.


BFS를 이용한 방법

에디토리얼에서도 이걸 정해로 주장하고 있다.

뭐 기본적으로 DFS와 동일한 아이디어 인데, 최대숫자를 guessing할 필요가 없고 그냥, 값이 채워진게 10만번째이면 바로 break하면 되기 때문에 좀 더 안전성이 있다. 부채모양으로 퍼져나가니 찾자마자 최단거리가 되는 원리랑 조금 비슷한게 담긴거 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
map<ll, int> m;
int main()
{
    int k; cin >> k;
    queue<ll> q;
    for (int i = 1; i < 10; i++) q.push(i);
    while (q.size()) {
        ll n = q.front(); q.pop();
        m[n] = 1;
        if (m.size() > 100000break;
        if(n%10!=0) q.push(n * 10 + n % 10 - 1);
        q.push(n * 10 + n % 10);
        if(n%10!=9) q.push(n * 10 + n % 10 + 1);
    }
    int ix = 1;
    for (auto a : m) {
        if (ix++ == k) cout << a.first << endl;
    }
    return 0;
}
cs

실전에서는 이코드처럼 정확히 10만에서 break하면 좀 위험할수도 있으니, 좀더 버퍼를 주는게 좋겠지만, 어쨌든 DFS보다는 나은 어프로치인듯하다.

덕북에 실행속도와 메모리 사용량에 있어서도 3배정도는 이득이 있는듯?


아래는 다른사람들 BFS구현

https://atcoder.jp/contests/abc161/submissions/11513177

https://atcoder.jp/contests/abc161/submissions/11518213

이진탐색을 이용한 방법

이진탐색+DigitDP 솔루션 : https://atcoder.jp/contests/abc161/submissions/11532810

이건 오버 엔지니어링 같아서 보기가 좀 싫어지네 ㅎ 나중에 보자.


반응형

'Programming > Problem Solving' 카테고리의 다른 글

BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09
Visual Studio Code  (0) 2020.04.03
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (0) 2020.03.30

맥에서 코딩하기 위해, Visual Studio Code를 세팅해보았다.


https://ldgeao99.tistory.com/203 이 링크가 가장 도움이 됐지만 일부 세팅은 다시 해줘야 했다(디버깅용 -g 옵션, a.out 등)


tasks.jon과 launch.json이 필요한데.. 현재 내 설정 공개한다.


tasks.jon

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
{
    "version": "2.0.0",
    "runner": "terminal",
    "type": "shell",
    "echoCommand": true,
    "presentation" : { "reveal": "always" },
    "tasks": [
          //C++ 컴파일
          {
            "label": "C++빌드하자",
            "command": "g++",
            "args": [
                "-g",
                "-std=c++11",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}"
            ],
            "group": "build",
 
            //컴파일시 에러를 편집기에 반영
            //참고:   https://code.visualstudio.com/docs/editor/tasks#_defining-a-problem-matcher
 
            "problemMatcher": {
                "fileLocation": [
                    "relative",
                    "${workspaceRoot}"
                ],
                "pattern": {
                    // The regular expression. 
                   //Example to match: helloWorld.c:5:3: warning: implicit declaration of function 'prinft'
                    "regexp": "^(.*):(\\d+):(\\d+):\\s+(warning error):\\s+(.*)$",
                    "file": 1,
                    "line": 2,
                    "column": 3,
                    "severity": 4,
                    "message": 5
                }
            }
        },
        {
 
            "label": "실행",
            "command": "cd ${fileDirname} && ./${fileBasenameNoExtension}",
            "group": "test"
        }
    ]
}
cs


launch.jon

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
{
    // IntelliSense를 사용하여 가능한 특성에 대해 알아보세요.
    // 기존 특성에 대한 설명을 보려면 가리킵니다.
    // 자세한 내용을 보려면 https://go.microsoft.com/fwlink/?linkid=830387을(를) 방문하세요.
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(lldb) 연결",
            "type": "cppdbg",
            "request": "attach",
            "program": "${workspaceFolder}/a.out",
            "processId": "${command:pickProcess}",
            "MIMode": "lldb"
        },
        {
            "name": "(lldb) 시작",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}/a",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "lldb"
        }
    ]
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (0) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15

탑코더할때는 moj를 많이 썼는데, 자동으로 내 템플릿코드 가져오고, testcase 빌드할 수 있게 해주는등 온라인저지 이용시 시간단축에 도움이 된다.


코드포스로 옮기면서 비슷한걸 찾아봤는데 VsCaide라는걸 찾았다.


그냥 visual studio 2019에서 확장 > 확장관리 들어가서 vscaide로 검색하고 설치하면 된다 (간단)



반응형

'Programming > Problem Solving' 카테고리의 다른 글

[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
Visual Studio Code  (0) 2020.04.03
C++ bigint class  (0) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01

여기나온게 지금까지 내가 알기로는 가장 좋다.

내 github에도 저장해두었다.

아래는 bigint를 사용한 A+B샘플(백준15740문제의 답안이기도 하다)

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
#include <bits/stdc++.h>
using namespace std;
/*
  ######################################################################
  #######################   THE   BIG   INT   ##########################
*/
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
    vector<int> a;
    int sign;
    /*<arpa>*/
    int size() {
        if (a.empty())return 0;
        int ans = (a.size() - 1* base_digits;
        int ca = a.back();
        while (ca)
            ans++, ca /= 10;
        return ans;
    }
    bigint operator ^(const bigint& v) {
        bigint ans = 1, a = *this, b = v;
        while (!b.isZero()) {
            if (b % 2)
                ans *= a;
            a *= a, b /= 2;
        }
        return ans;
    }
    string to_string() {
        stringstream ss;
        ss << *this;
        string s;
        ss >> s;
        return s;
    }
    int sumof() {
        string s = to_string();
        int ans = 0;
        for (auto c : s)  ans += c - '0';
        return ans;
    }
    /*</arpa>*/
    bigint() :
        sign(1) {
    }
 
    bigint(long long v) {
        *this = v;
    }
 
    bigint(const string& s) {
        read(s);
    }
 
    void operator=(const bigint& v) {
        sign = v.sign;
        a = v.a;
    }
 
    void operator=(long long v) {
        sign = 1;
        a.clear();
        if (v < 0)
            sign = -1, v = -v;
        for (; v > 0; v = v / base)
            a.push_back(v % base);
    }
 
    bigint operator+(const bigint& v) const {
        if (sign == v.sign) {
            bigint res = v;
 
            for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i) {
                if (i == (int)res.a.size())
                    res.a.push_back(0);
                res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
                carry = res.a[i] >= base;
                if (carry)
                    res.a[i] -= base;
            }
            return res;
        }
        return *this - (-v);
    }
 
    bigint operator-(const bigint& v) const {
        if (sign == v.sign) {
            if (abs() >= v.abs()) {
                bigint res = *this;
                for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i) {
                    res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
                    carry = res.a[i] < 0;
                    if (carry)
                        res.a[i] += base;
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }
 
    void operator*=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(int v) const {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    void operator*=(long long v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(long long v) const {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1) {
        int norm = base / (b1.a.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.a.resize(a.a.size());
 
        for (int i = a.a.size() - 1; i >= 0; i--) {
            r *= base;
            r += a.a[i];
            int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
            int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
            int d = ((long long)base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.a[i] = d;
        }
 
        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }
 
    bigint operator/(const bigint& v) const {
        return divmod(*this, v).first;
    }
 
    bigint operator%(const bigint& v) const {
        return divmod(*this, v).second;
    }
 
    void operator/=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int)a.size() - 1, rem = 0; i >= 0--i) {
            long long cur = a[i] + rem * (long long)base;
            a[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        trim();
    }
 
    bigint operator/(int v) const {
        bigint res = *this;
        res /= v;
        return res;
    }
 
    int operator%(int v) const {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = a.size() - 1; i >= 0--i)
            m = (a[i] + m * (long long)base) % v;
        return m * sign;
    }
 
    void operator+=(const bigint& v) {
        *this = *this + v;
    }
    void operator-=(const bigint& v) {
        *this = *this - v;
    }
    void operator*=(const bigint& v) {
        *this = *this * v;
    }
    void operator/=(const bigint& v) {
        *this = *this / v;
    }
 
    bool operator<(const bigint& v) const {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size()* v.sign;
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }
 
    bool operator>(const bigint& v) const {
        return v < *this;
    }
    bool operator<=(const bigint& v) const {
        return !(v < *this);
    }
    bool operator>=(const bigint& v) const {
        return !(*this < v);
    }
    bool operator==(const bigint& v) const {
        return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint& v) const {
        return *this < v || v < *this;
    }
 
    void trim() {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }
 
    bool isZero() const {
        return a.empty() || (a.size() == 1 && !a[0]);
    }
 
    bigint operator-() const {
        bigint res = *this;
        res.sign = -sign;
        return res;
    }
 
    bigint abs() const {
        bigint res = *this;
        res.sign *= res.sign;
        return res;
    }
 
    long long longValue() const {
        long long res = 0;
        for (int i = a.size() - 1; i >= 0; i--)
            res = res * base + a[i];
        return res * sign;
    }
 
    friend bigint gcd(const bigint& a, const bigint& b) {
        return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint& a, const bigint& b) {
        return a / gcd(a, b) * b;
    }
 
    void read(const string& s) {
        sign = 1;
        a.clear();
        int pos = 0;
        while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = s.size() - 1; i >= pos; i -= base_digits) {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        trim();
    }
 
    friend istream& operator>>(istream& stream, bigint& v) {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }
 
    friend ostream& operator<<(ostream& stream, const bigint& v) {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int)v.a.size() - 2; i >= 0--i)
            stream << setw(base_digits) << setfill('0'<< v.a[i];
        return stream;
    }
 
    static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits) {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0= 1;
        for (int i = 1; i < (int)p.size(); i++)
            p[i] = p[i - 1* 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int)a.size(); i++) {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits) {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while (!res.empty() && !res.back())
            res.pop_back();
        return res;
    }
 
    typedef vector<long long> vll;
 
    static vll karatsubaMultiply(const vll& a, const vll& b) {
        int n = a.size();
        vll res(n + n);
        if (n <= 32) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }
 
        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());
 
        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);
 
        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];
 
        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int)a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            r[i] -= a2b2[i];
 
        for (int i = 0; i < (int)r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < (int)a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return res;
    }
 
    bigint operator*(const bigint& v) const {
        vector<int> a6 = convert_base(this->a, base_digits, 6);
        vector<int> b6 = convert_base(v.a, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while (a.size() < b.size())
            a.push_back(0);
        while (b.size() < a.size())
            b.push_back(0);
        while (a.size() & (a.size() - 1))
            a.push_back(0), b.push_back(0);
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < (int)c.size(); i++) {
            long long cur = c[i] + carry;
            res.a.push_back((int)(cur % 1000000));
            carry = (int)(cur / 1000000);
        }
        res.a = convert_base(res.a, 6, base_digits);
        res.trim();
        return res;
    }
};
/*
  #######################   THE   BIG   INT   ##########################
  ######################################################################
*/
 
 
 
 
string a, b;
int main(void)
{
    cin >> a >> b;
    bigint A(a), B(b), C;
    C = A + B;
    cout << C.to_string() << endl;
    return 0;
}
 
 
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

Visual Studio Code  (0) 2020.04.03
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21

문제는 여기






퀸은 배치된 칸을 기준으로 가로,세로, 그리고 대각선 이동이 가능한 가장 가치있는 말로 다음 빨간선과 같이 움직인다.





다음은 N이 8일때 해 중의 하나이다.



만약 모든 경우의 수에 대해서 재귀를 통해 브루트포스 방식으로 구한다음에 해인지 아닌지를 말단에서 체크하게 되면, DFS가 되는데, 

N=8인 경우 체스판의 칸 개수가 8x8=64개이고 이중에 8개를 고르는 조합의 수가 되므로 $_{64}C_8 = 4,426,165,368$이 되어 44억이 넘어갑니다. 이중에 92개만이 정답이죠.


가로로 겹치지 않게 한줄에 하나의 queen만 놓는식으로 가지치기(백트래킹)를 하게되면 $8^8 = 16,777,216$으로 줄어듭니다. (천6백만)


세로로도 겹치지 않게 permutation을 사용하는 백트래킹의 경우 $8! = 40,320$이 되어 훨씬 줄어듭니다.


다음과 같이 한줄씩 보면서 가로,세로,대각선 모두에 대해 백트래킹을 사용하면 5,508정도로 더 줄어듭니다.


이 문제의 경우 이정도 가지치기를 하면 제한시간내에 맞았습니다를 받을 수 있습니다.





소스코드는 다음과 같습니다.

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 <bits/stdc++.h>
using namespace std;
 
int N;
int vx[15+1], vy[15+1];
 
int go(int y, int x)
{
    //check valid (back tracking)
    for (int i = 0; i < y; i++) {
        if (y == vy[i] || x == vx[i]) return 0;  //직선겹침
        if (abs(x - vx[i]) == abs(y - vy[i])) return 0//대각겹침
    }
 
    //terminal condition
    if (y == N - 1return 1;
 
    //now record position
    vy[y] = y, vx[y] = x;
 
    //loop
    int r = 0;
    for (int i = 0; i < N; i++) {
        r += go(y + 1, i);
    }
 
    return r;
}
 
int main(void)
{
    scanf("%d"&N);
    int r = 0;
    for (int i = 0; i < N; i++) r += go(0, i);
    printf("%d\n", r);
    return 0;
}
cs






반응형

'Programming > Problem Solving' 카테고리의 다른 글

코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (0) 2020.03.30
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21
백준 팁모음  (0) 2019.03.18

+ Recent posts