[2529] 부등호
### Stack ###
[2529] 부등호 : http://boj.kr/2529
<소스코드>
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 | #include <stdio.h> int main() { int n; int nextL=8, nextS=1; long long int ansL=9LL, ansS=0LL, ans=0LL; long long int arrL[10], arrS[10]; int Lidx=0, Sidx=0; char buf[10]; int factL=10, factS=10; scanf("%d", &n); for(int i=0; i<n; i++) { char ch; scanf(" %c", &ch); if(ch == '<') { if(i == n-1 && nextL == 0) arrL[Lidx++] = 0LL; ansL = 1LL*nextL*factL + ansL; arrS[Sidx++] = ansS; ansS = nextS; factS = 1; } else { arrL[Lidx++] = ansL; ansL = nextL; factL = 1; ansS = 1LL*nextS*factS + ansS; } nextL--; factL *= 10; nextS++; factS *= 10; } arrL[Lidx++] = ansL; arrS[Sidx++] = ansS; for(int i=0; i<Lidx; i++) printf("%lld", arrL[i]); puts(""); for(int i=0; i<Sidx; i++) printf("%lld", arrS[i]); puts(""); return 0; } | cs |
>> 큰수의 경우 '>' 를 만나기 전까지 앞에다 갱신을 해주면 된다 '<' 를 만나면 남은 최대값으로 반복.
>> 알고리즘 분류에 그리디와 위상정렬로 되어 있고, kks227 님도 위상정렬로 해설을 하셨는데,
한편으로 그리디는 맞다고 생각하지만, 위상정렬은 왜 위상정렬인지 아직도 모르겠다.
>> 그럼에도 불구하고 스택으로 분류를 한 이유는 다른 사람이 스택으로 풀었기 때문이고, 아이디어는 내가 푼 것과 비슷하기 때문이다.
>> 그분이 더 머리가 좋아보인다...ㅜ (아래는 그 코드)
- coded by t1234
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 <cstdio> #include <stack> int k, n=9; char a[15]; std::stack<int> st; void f() { while(!st.empty()) printf("%d", st.top()), st.pop(); } int main() { int i; scanf("%d", &k); st.push(n--); for(i=0; i<k; i++) { scanf("%s", &a[i]); if(a[i]=='>') f(); st.push(n--); } f(); puts(""); n = 0; st.push(n++); for(i=0; i<k; i++) { if(a[i]=='<') f(); st.push(n++); } f(); return 0; } | cs |
'BOJ > Data Structure' 카테고리의 다른 글
[5639] 이진 검색 트리 (0) | 2018.07.22 |
---|---|
[1655] 가운데를 말해요 (0) | 2018.07.22 |
[11985] 오렌지 출하
### DP ###
[11985] 오렌지 출하 : http://boj.kr/11985
<소스코드>
d[i] : i번째 오랜지부터 포장했을 때, 비용의 최소값.
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 | #include <stdio.h> int a[20001]; long long d[21001]; int n, m, k; long long min(long long a, long long b) { return a < b ? a : b; } long long orange(int s, int e) { long long *ret = &d[s]; int size, big=0, small=0x7fffffff; long long box; if(s >= e) return 0; if(*ret != -1) return *ret; *ret = 0x7fffffffffffffff; size = m < e-s+1 ? m : e-s+1; for(int i=0; i<size; i++) { if(big < a[s+i]) big = a[s+i]; if(small > a[s+i]) small = a[s+i]; box = 1LL*(i+1)*(big-small) + k; *ret = min(*ret, box+orange(s+i+1, e)); } return *ret; } int main() { scanf("%d%d%d", &n, &m, &k); for(int i=0; i<n; i++) { scanf("%d", a+i); d[i] = -1; } printf("%lld\n", orange(0, n)); return 0; } | cs |
>> 시간복잡도 : O(NM)
'BOJ > DP' 카테고리의 다른 글
[9177] 단어 섞기 (0) | 2018.05.22 |
---|---|
[2602] 돌다리 건너기 (0) | 2018.05.17 |
[9252] LCS2 (0) | 2018.04.22 |
[9251] LCS (0) | 2018.04.21 |
[14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[3063] 게시판
[3063] 게시판 : http://boj.kr/3063
### ACM-ICPC > Asia Regional - Daejeon Nationalwide Internet Competition 2002 A번 ###
참고 : https://fatc.club/2017/03/01/827
<소스코드>
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 | #include <stdio.h> int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int main() { int n; scanf("%d", &n); while(n--) { int ans, diff; int x1, y1, x2, y2; int x3, y3, x4, y4; int lbx, lby, rtx, rty; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); scanf("%d%d%d%d", &x3, &y3, &x4, &y4); ans = (x2-x1)*(y2-y1); rtx = min(x2, x4); rty = min(y2, y4); lbx = max(x1, x3); lby = max(y1, y3); diff = (rtx-lbx)*(rty-lby); printf("%d\n", ans-diff); } return 0; } | cs |
>> 경우의 수는 10가지. 그림을 그려보니 규칙이 보인다.
>> 우상의 좌표들은 x2, x4 혹은 y2, y4 중 하나이고,
좌하의 좌표들은 x11, x3 혹은 y1, y3 중 하나이다.
- 메모리 초과 코드
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 | #include <stdio.h> int poster[10001][10001]; int main() { int n; scanf("%d", &n); while(n--) { int ans=0; int x1, y1, x2, y2; int x3, y3, x4, y4; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); for(int x=x1; x<x2; x++) for(int y=y1; y<y2; y++) poster[x][y] = 1; scanf("%d%d%d%d", &x3, &y3, &x4, &y4); for(int x=x3; x<x4; x++) for(int y=y3; y<y4; y++) poster[x][y] = 0; for(int x=x1; x<x2; x++) for(int y=y1; y<y2; y++) if(poster[x][y] == 1) ans++; printf("%d\n", ans); } return 0; } | cs |
>> 배열 10000 * 10000 은 역시 오바였다.
[1021] 회전하는 큐
[1021] 회전하는 큐 : http://boj.kr/1021
### 시뮬레이션 ###
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); vector<int> v; for(int i=1; i<=n; i++) v.push_back(i); int cur=0, ans=0; for(int i=0; i<m; i++) { int target, tmp = 0; int size = v.size(); scanf("%d", &target); for(int j=0; j<size; j++) { if(v[cur] == target) { v.erase(v.begin()+cur); if(cur == size-1) cur = 0; break; } cur = (cur+1)%size; tmp++; } ans += min(tmp, size-tmp); } printf("%d\n", ans); } | cs |
>> 24 라인이 중요한 것 같다. 중간에 있는 벡터를 삭제하면 자동으로 앞당겨져 cur 에 저장되어 있는 인덱스를 변경할 필요가 없지만,
맨 마지막 데이터가 삭제되면 cur 의 인덱스를 0으로 변경해야 한다.
[9177] 단어 섞기
[9177] 단어 섞기 : http://boj.kr/9177
### DP ###
d[i][j] : 문자열 a의 i번째, 문자열 b의 j번째 인덱스에서 시작해서 단어를 섞어 세번째 문자열을 만들 수 있는지 여부.
<소스코드>
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 <stdio.h> #include <string.h> int aLen, bLen; char a[201], b[201], c[401]; int d[201][201]; int word(int aIdx, int bIdx, int cIdx) { int *ret = &d[aIdx][bIdx]; if(aIdx == aLen && bIdx == bLen) return 1; if(*ret != -1) return *ret; *ret = 0; if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1); if(*ret) return *ret; if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1); return *ret; } int main() { int n; scanf("%d", &n); for(int tc=1; tc<=n; tc++) { scanf("%s%s%s", a, b, c); printf("Data set %d: ", tc); aLen = strlen(a); bLen = strlen(b); memset(d, -1, sizeof(d)); word(0, 0, 0) ? puts("yes") : puts("no"); } return 0; } | cs |
>> 처음에는 그리디방식으로 햇는데, 두번째 테케가 반례가 되어버렸다.
>> 유형이 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 33 34 35 36 37 38 39 40 | #include <stdio.h> #include <string.h> int aLen, bLen; char a[201], b[201], c[401]; int d[201][201][401]; int word(int aIdx, int bIdx, int cIdx) { int *ret = &d[aIdx][bIdx][cIdx]; if(aIdx == aLen && bIdx == bLen) return 1; if(*ret != -1) return *ret; *ret = 0; if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1); if(*ret) return *ret; if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1); return *ret; } int main() { int n; scanf("%d", &n); for(int tc=1; tc<=n; tc++) { int ai=0, bi=0, ci=0; scanf("%s%s%s", a, b, c); printf("Data set %d: ", tc); aLen = strlen(a); bLen = strlen(b); memset(d, -1, sizeof(d)); word(0, 0, 0) ? puts("yes") : puts("no"); } return 0; } | cs |
>> AC 받은 코드와 차이가 있다면 cache 역할을 하는 배열을 3차원으로 잡은것. 생각해보면 2차원으로 충분하단 생각이 들었다.
>> 그리고 시간초과 난 이유를 곰곰히 생각해보니, 매 테케마다(n*200*200*400에 해당하는) memset() 을 돌려 그런 것 같아.
'BOJ > DP' 카테고리의 다른 글
[11985] 오렌지 출하 (0) | 2018.06.21 |
---|---|
[2602] 돌다리 건너기 (0) | 2018.05.17 |
[9252] LCS2 (0) | 2018.04.22 |
[9251] LCS (0) | 2018.04.21 |
[14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[4803] 트리 : http://boj.kr/4803
- 정점의 갯수를 세고, 간선의 갯수를 센다.
- 트리는 정점의 갯수-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 64 65 66 67 68 69 | #include <cstdio> #include <cstring> #include <vector> using namespace std; int n, m; bool visited[501]; bool check[501]; int dfsV(vector<int> v[], int s) { int ret = 1; visited[s] = 1; for(int i=0; i<v[s].size(); i++) { int next = v[s][i]; if(!visited[next]) ret += dfsV(v, next); } return ret; } int dfsE(vector<int> v[], int s) { int ret=v[s].size(); check[s] = 1; for(int i=0; i<v[s].size(); i++) { int next = v[s][i]; if(!check[next]) ret += dfsE(v, next); } return ret; } int main() { int tc=0; while(1) { int ans=0; scanf("%d%d", &n, &m); if(!n && !m) break; vector<int> v[501]; while(m--) { int a, b; scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } memset(visited, 0, sizeof(visited)); memset(check, 0, sizeof(check)); for(int i=1; i<=n; i++) { if(!visited[i]) { int vertex = dfsV(v, i); int edge = dfsE(v, i); if(vertex-1 == edge/2) ans++; } } tc++; printf("Case %d: ", tc); if(ans == 0) puts("No trees."); else if(ans == 1) puts("There is one tree."); else printf("A forest of %d trees.\n", ans); } return 0; } | cs |
<예전코드>
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 | #include <cstdio> #include <vector> using namespace std; int v, e; void dfs(vector<int> g[], bool visited[], int cur) { visited[cur] = true; v++; for(int i=0; i<g[cur].size(); i++) { int next = g[cur][i]; e++; if(!visited[next]) { dfs(g, visited, next); } } } int main() { int tc=1; while(1) { int n, m; scanf("%d %d", &n, &m); if(!n && !m) break; vector<int> g[501]; while(m--) { int a, b; scanf("%d %d", &a, &b); g[a].push_back(b); g[b].push_back(a); } int ans=0; bool visited[501]={0}; for(int i=1; i<=n; i++) { if(!visited[i]) { v = e = 0; dfs(g, visited, i); if(v-1 == e/2) ans++; } } printf("Case %d: ", tc++); if(!ans) puts("No trees."); else ans > 1 ? printf("A forest of %d trees.\n", ans) : puts("There is one tree."); } return 0; } | cs |
>> dfs 를 한번만 호출해서 정점의 수와 간선의 수를 카운트했다.
'BOJ > Tree' 카테고리의 다른 글
[11725] 트리의 부모 찾기 (0) | 2018.05.20 |
---|---|
[1991] 트리 순회 (0) | 2018.05.20 |
[11725] 트리의 부모 찾기
[11725] 트리의 부모 찾기 : http://boj.kr/11725
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; int main() { int n; scanf("%d", &n); vector<int> v[100001]; for(int i=1; i<n; i++) { int a, b; scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } vector<int> p(n+1, 0); queue<int> q; q.push(1); p[1] = -1; while(!q.empty()) { int parent = q.front(); q.pop(); for(int i=0; i<v[parent].size(); i++) { int child = v[parent][i]; if(!p[child]) { q.push(child); p[child] = parent; } } } for(int i=2; i<=n; i++) printf("%d\n", p[i]); return 0; } | cs |
>> 부모를 찾지 못했다면 큐에 넣고 부모 저장. BFS.
'BOJ > Tree' 카테고리의 다른 글
[4803] 트리 (0) | 2018.05.21 |
---|---|
[1991] 트리 순회 (0) | 2018.05.20 |
[1991] 트리 순회
[1991] 트리 순회 : http://boj.kr/1991
<소스코드>
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> char tree[26][2]; void pre(int root) { if(root == '.') return ; printf("%c", root+'A'); pre(tree[root][0]); pre(tree[root][1]); } void in(int root) { if(root == '.') return ; in(tree[root][0]); printf("%c", root+'A'); in(tree[root][1]); } void post(int root) { if(root == '.') return ; post(tree[root][0]); post(tree[root][1]); printf("%c", root+'A'); } int main() { int n; scanf("%d", &n); while(n--) { char p, lc, rc; scanf(" %c %c %c", &p, &lc, &rc); tree[p-'A'][0] = lc == '.' ? lc : lc-'A'; tree[p-'A'][1] = rc == '.' ? rc : rc-'A'; } pre(0); puts(""); in(0); puts(""); post(0); puts(""); return 0; } | cs |
'BOJ > Tree' 카테고리의 다른 글
[4803] 트리 (0) | 2018.05.21 |
---|---|
[11725] 트리의 부모 찾기 (0) | 2018.05.20 |
[2602] 돌다리 건너기
[2602] 돌다리 건너기 : http://boj.kr/2602
- 난 3차원으로 풀었는데, 다른 사람들은 2차원으로 풀었다.
d[bidx][ad][sidx] : 상태가 ad(0은 천사차례, 1은 악마차례) 일때,
bidx번째 돌다리에서, sidx 번째 문자부터 시작하는 문자열에 적힌 순서대로 다리를 건널 수 있는 방법의 수
<소스코드>
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 | #include <stdio.h> char str[21]; char ang[101], dev[101]; int d[101][2][21]; int bridge(int bidx, int ad, int sidx) { int *ret = &d[bidx][ad][sidx]; if(!str[sidx]) return 1; if(ad == 0 && !ang[bidx]) return 0; if(ad == 1 && !dev[bidx]) return 0; if(*ret) return *ret; if(ad == 0) { if(ang[bidx] == str[sidx]) *ret = bridge(bidx+1, !ad, sidx+1); *ret += bridge(bidx+1, ad, sidx); } else { if(dev[bidx] == str[sidx]) *ret = bridge(bidx+1, !ad, sidx+1); *ret += bridge(bidx+1, ad, sidx); } return *ret; } int main() { scanf("%s%s%s", str, ang, dev); printf("%d\n", bridge(0, 0, 0)+bridge(0, 1, 0)); return 0; } | cs |
>> 천사다리를 먼저 택한 경우 + 악마다리를 먼저 택한 경우
'BOJ > DP' 카테고리의 다른 글
[11985] 오렌지 출하 (0) | 2018.06.21 |
---|---|
[9177] 단어 섞기 (0) | 2018.05.22 |
[9252] LCS2 (0) | 2018.04.22 |
[9251] LCS (0) | 2018.04.21 |
[14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[5883] 아이폰 9S
[5883] 아이폰 9S : http://boj.kr/5883
- 입력으로 들어오는 수를 체크해 놓고, 큐에 저장.
- 큐에서 꺼낸 다음, 이미 사용한 적이 있으면 continue
- 큐에서 꺼낸 값을 제외하고, 가장 길게 연속하는 수를 세가며 갱신.
<소스코드>
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 | #include <stdio.h> int a[1001]; int check[1000001]; int q[1001], f, r; int main() { int n, ans=1; scanf("%d", &n); for(int i=0; i<n; i++) { scanf("%d", a+i); check[a[i]] = 1; q[r++] = a[i]; } while(f != r) { int cnt = 1; int cur = a[0]; int exp = q[f++]; if(!check[exp]) continue; check[exp] = 0; for(int i=1; i<n; i++) { if(a[i] == exp) continue; if(cur == a[i]) cnt++; else { if(ans < cnt) ans = cnt; cur = a[i]; cnt = 1; } } if(ans < cnt) ans = cnt; } printf("%d\n", ans); return 0; } | cs |