8000 add Appendix E · dkim-coder/basic-algo-lecture@d4e38f2 · GitHub
[go: up one dir, main page]
Skip to content

Commit d4e38f2

Browse files
encrypted-defencrypted-def
committed
add Appendix E
1 parent 508c170 commit d4e38f2

24 files changed

+690
-31
lines changed

‎0x15/solutions/1351.cpp

Lines changed: 0 additions & 31 deletions
This file was deleted.

‎0x1A/solutions/1005_1.cpp

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
// Authored by : BaaaaaaaaaaarkingDog
2+
// Co-authored by : -
3+
// http://boj.kr/643416ff30264d9fb1290fb046114b8c
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
int n, k, w;
8+
int a[1005];
9+
int d[1005];
10+
vector<int> adj[1005];
11+
12+
int go(int x){
13+
if(d[x] != -1)
14+
return d[x];
15+
16+
d[x] = 0;
17+
for(int nxt : adj[x])
18+
d[x] = max(d[x], go(nxt));
19+
20+
return d[x] = d[x] + a[x];
21+
}
22+
23+
int main(){
24+
ios::sync_with_stdio(0);
25+
cin.tie(0);
26+
27+
fill(d, d+1001, -1);
28+
int t;
29+
cin >> t;
30+
while(t--){
31+
cin >> n >> k;
32+
for(int i = 1; i <= n; i++)
33+
cin >> a[i];
34+
while(k--){
35+
int u, v;
36+
cin >> u >> v;
37+
adj[v].push_back(u);
38+
}
39+
cin >> w;
40+
cout << go(w) << '\n';
41+
42+
fill(d, d+n+1, -1);
43+
for(int i = 1; i <= n; i++)
44+
adj[i].clear();
45+
}
46+
}
47+
48+
/*
49+
top-down 방식을 이용한 코드. 자세한 설명은
50+
Appendix E - 다이나믹 프로그래밍 심화 강의 참고.
51+
*/

‎Appendix E/1005.cpp

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
// http://boj.kr/643416ff30264d9fb1290fb046114b8c
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
int n, k, w;
6+
int a[1005];
7+
int d[1005];
8+
vector<int> adj[1005];
9+
10+
int go(int x){
11+
if(d[x] != -1)
12+
return d[x];
13+
14+
d[x] = 0;
15+
for(int nxt : adj[x])
16+
d[x] = max(d[x], go(nxt));
17+
18+
return d[x] = d[x] + a[x];
19+
}
20+
21+
int main(){
22+
ios::sync_with_stdio(0);
23+
cin.tie(0);
24+
25+
fill(d, d+1001, -1);
26+
int t;
27+
cin >> t;
28+
while(t--){
29+
cin >> n >> k;
30+
for(int i = 1; i <= n; i++)
31+
cin >> a[i];
32+
while(k--){
33+
int u, v;
34+
cin >> u >> v;
35+
adj[v].push_back(u);
36+
}
37+
cin >> w;
38+
cout << go(w) << '\n';
39+
40+
fill(d, d+n+1, -1);
41+
for(int i = 1; i <= n; i++)
42+
adj[i].clear();
43+
}
44+
}

‎Appendix E/solutions/1005.cpp

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
// Authored by : BaaaaaaaaaaarkingDog
2+
// Co-authored by : -
3+
// http://boj.kr/643416ff30264d9fb1290fb046114b8c
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
int n, k, w;
8+
int a[1005];
9+
int d[1005];
10+
vector<int> adj[1005];
11+
12+
int go(int x){
13+
if(d[x] != -1)
14+
return d[x];
15+
16+
d[x] = 0;
17+
for(int nxt : adj[x])
18+
d[x] = max(d[x], go(nxt));
19+
20+
return d[x] = d[x] + a[x];
21+
}
22+
23+
int main(){
24+
ios::sync_with_stdio(0);
25+
cin.tie(0);
26+
27+
fill(d, d+1001, -1);
28+
int t;
29+
cin >> t;
30+
while(t--){
31+
cin >> n >> k;
32+
for(int i = 1; i <= n; i++)
33+
cin >> a[i];
34+
while(k--){
35+
int u, v;
36+
cin >> u >> v;
37+
adj[v].push_back(u);
38+
}
39+
cin >> w;
40+
cout << go(w) << '\n';
41+
42+
fill(d, d+n+1, -1);
43+
for(int i = 1; i <= n; i++)
44+
adj[i].clear();
45+
}
46+
}

‎Appendix E/solutions/10942.cpp

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
// Authored by : Hot6Mania
2+
// Co-authored by : -
3+
// http://boj.kr/2b8c4fa5fed849008ff86212e8be86b3
4+
5+
#include <bits/stdc++.h>
6+
using namespace std;
7+
8+
int n;
9+
int a[2010], d[2010][2010];
10+
11+
int main(void) {
12+
ios::sync_with_stdio(0);
13+
cin.tie(0);
14+
15+
cin >> n;
16+
for (int i = 1; i <= n; ++i) cin >> a[i];
17+
18+
for (int i = 1; i <= n; ++i) {
19+
d[i][i] = 1;
20+
if (a[i - 1] == a[i]) d[i - 1][i] = 1;
21+
}
22+
23+
for (int gap = 2; gap < n; ++gap) {
24+
for (int i = 1; i <= n - gap; ++i) {
25+
int s = i, e = i + gap;
26+
if (a[s] == a[e] && d[s + 1][e - 1]) d[s][e] = 1;
27+
}
28+
}
29+
30+
int t;
31+
cin >> t;
32+
while (t--) {
33+
int s, e;
34+
cin >> s >> e;
35+
cout << d[s][e] << '\n';
36+
}
37+
38+
return 0;
39+
}

‎Appendix E/solutions/11660.cpp

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
// Authored by : Hot6Mania
2+
// Co-authored by : -
3+
// http://boj.kr/4464384189904471b2a6b8d65681bbd4
4+
5+
#include <bits/stdc++.h>
6+
using namespace std;
7+
8+
int n, m;
9+
int a[1030][1030], d[1030][1030];
10+
11+
int main(void){
12+
ios::sync_with_stdio(0);
13+
cin.tie(0);
14+
15+
cin >> n >> m;
16+
for (int i = 1; i <= n; ++i){
17+
for (int j = 1; j <= n; ++j){
18+
cin >> a[i][j];
19+
d[i][j] = d[i-1][j] + d[i][j-1] - d[i-1][j-1] + a[i][j];
20+
}
21+
}
22+
23+
while(m--){
24+
int x1, y1, x2, y2;
25+
cin >> x1 >> y1 >> x2 >> y2;
26+
cout << d[x2][y2] - d[x1-1][y2] - d[x2][y1-1] + d[x1-1][y1-1] << '\n';
27+
}
28+
}

‎Appendix E/solutions/12865.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
// Authored by : BaaaaaaaaaaarkingDog
2+
// Co-authored by : -
3+
// http://boj.kr/485b69efb085449ca4c64d848656498b
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
int n, k;
8+
int d[102][100002];
9+
int w[102];
10+
int v[102];
11+
12+
int main(void) {
13+
ios::sync_with_stdio(0);
14+
cin.tie(0);
15+
16+
cin >> n >> k;
17+
for(int i = 0; i < n; i++)
18+
cin >> w[i] >> v[i];
19+
20+
for(int i = 0; i < n; i++){
21+
for(int j = 1; j <= k; j++){
22+
if(i-1 >= 0)
23+
d[i][j] = d[i-1][j];
24+
if(j-w[i] >= 0){
25+
if(i-1 >= 0)
26+
d[i][j] = max(d[i][j], d[i-1][j-w[i]] + v[i]);
27+
else
28+
d[i][j] = v[i];
29+
}
30+
}
31+
}
32+
cout << d[n-1][k];
33+
}

‎Appendix E/solutions/1351.cpp

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// Authored by : BaaaaaaaaaaarkingDog
2+
// Co-authored by : -
3+
// http://boj.kr/5a8c26a75fd7433da8b814fc477b0317
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
using ll = long long;
8+
ll n, p, q;
9+
map<ll, ll> a;
10+
11+
ll go(ll x){
12+
if(a[x] != 0)
13+
return a[x];
14+
if(x == 0)
15+
return a[x] = 1;
16+
return a[x] = go(x/p) + go(x/q);
17+
}
18+
19+
int main(void) {
20+
ios::sync_with_stdio(0);
21+
cin.tie(0);
22+
23+
cin >> n >> p >> q;
24+
cout << go(n);
25+
}

‎Appendix E/solutions/1520.cpp

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
10000
@@ -0,0 +1,35 @@
1+
// Authored by : Hot6Mania
2+
// Co-authored by : -
3+
// http://boj.kr/659c5fb01df043f6997a1aabc8a36f1b
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
int dx[4] = {1,0,-1,0};
8+
int dy[4] = {0,1,0,-1};
9+
int n, m;
10+
int a[505][505], d[505][505];
11+
12+
int func(int x, int y){
13+
if(d[x][y] != -1) return d[x][y];
14+
if(x == n - 1 && y == m - 1) return 1;
15+
int &ret = d[x][y];
16+
ret = 0;
17+
for(int dir = 0; dir < 4; ++dir){
18+
int nx = x + dx[dir];
19+
int ny = y + dy[dir];
20+
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
21+
if(a[x][y] > a[nx][ny]) ret += func(nx, ny);
22+
}
23+
return ret;
24+
}
25+
26+
int main(void){
27+
ios::sync_with_stdio(0);
28+
cin.tie(0);
29+
30+
cin >> n >> m;
31+
for(int i = 0; i < n; ++i)
32+
for(int j = 0; j < m; ++j)
33+
cin >> a[i][j], d[i][j] = -1;
34+
cout << func(0, 0);
35+
}

‎Appendix E/solutions/1699.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// Authored by : Hot6Mania
2+
// Co-authored by : -
3+
// http://boj.kr/56aaa902f66645c58a86798d210d1dd1
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
int n;
8+
int d[100010];
9+
10+
int main(void){
11+
ios::sync_with_stdio(0);
12+
cin.tie(0);
13+
14+
cin >> n;
15+
for(int i = 1; i <= n; ++i){
16+
d[i] = i;
17+
for(int j = 1; j * j <= i; ++j)
18+
d[i] = min(d[i], d[i - j * j] + 1);
19+
}
20+
cout << d[n];
21+
}

0 commit comments

Comments
 (0)
0