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



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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(){
    vector<pair<int,int>> order; // time, table num
    int N, M;
    
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        string s;
        int n,t;
        
        cin >> s;
        
        if(s == "order"){
            cin >> n >> t;
            order.push_back({t,n});
        }
        else if(s == "sort")
            sort(order.begin(), order.end());
        else if(s == "complete"){
            cin >> t;
            
            vector<pair<int,int>>::iterator iter;
            
            for(iter = order.begin(); iter != order.end(); iter++){
                if(t == (*iter).second){
                    order.erase(iter);
                    break;
                }
            }
        }
        
        if(order.empty())
            cout << "sleep\n";
        else{
            for(int j = 0; j < order.size(); j++)
                cout << order[j].second << ' ';
            cout << endl;
        }
 
            
    }
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[슬라이딩 윈도우] 백준 15831 준표의 조약돌  (0) 2018.12.31
[etc] 백준 15828 Router  (0) 2018.12.28
[재귀] 백준 11578 팀원 모집  (0) 2018.12.27
[etc] 백준 11575 Affine Cipher  (0) 2018.12.24
[bfs] 백준 15900 나무 탈출  (2) 2018.12.24

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


이런 탐색에는 재귀함수가 더 어울린다고 생각해서 재귀 함수를 이용해 풀었습니다.


재귀함수에 친해질 필요가 있겠네요.



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
#include <iostream>
using namespace std;
bool stu[11][11] = {0};
int chk[11] = {0};
int ret = 11;
int N = 0, M = 0;
 
int solve(int start, int num);
 
int main(){
    int O,t;
 
    chk[0] = true;
    cin >> N >> M;
 
    for(int i = 1; i <= M; i++){
        cin >> O;
        for(int j = 1; j <= O; j++){
            cin >> t;
            stu[i][t] = true;
        }
    }
    
    solve(0,0);
    
    if(ret == 11) cout << -1;
    else cout << ret;
}
 
int solve(int start, int num){
    bool chk2 = true;
    
    for(int i =1; i <= N; i++){
        if(stu[start][i]) chk[i] +=1;
    }
    
    for(int i = 1; i <= N; i++){
        if(chk[i]==0){
            chk2 = false; 
            break;
        }
    }
    
    if(chk2)
        return num;
    
    for(int i = start+1; i<=M; i++){
        ret= min(ret,solve(i,num+1));
        
        for(int j = 1; j <=N; j++)
            if(stu[i][j]) chk[j] -=1;
    }
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[etc] 백준 15828 Router  (0) 2018.12.28
[etc] 백준 14612 김식당  (0) 2018.12.28
[etc] 백준 11575 Affine Cipher  (0) 2018.12.24
[bfs] 백준 15900 나무 탈출  (2) 2018.12.24
[etc] 백준 15903 카드 합체 놀이  (0) 2018.12.22

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int a,b,T;
    string s;
    
    cin >> T;
    
    while(T--){
        cin >> a >> b;
        cin >> s;
        for(int i = 0; i < s.size(); i++){
            cout << char((((a*(s[i]-65)) + b) %26)+65);
        }
        cout << endl;
    }
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[etc] 백준 14612 김식당  (0) 2018.12.28
[재귀] 백준 11578 팀원 모집  (0) 2018.12.27
[bfs] 백준 15900 나무 탈출  (2) 2018.12.24
[etc] 백준 15903 카드 합체 놀이  (0) 2018.12.22
[ect] 백준 15904 UCPC는 무엇의 약자일까?  (0) 2018.12.22

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


처음에 풀었을 때는 시간 초과가 떴습니다.

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 <iostream>
#include <vector>
using namespace std;
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tr[500001]= {0}; tr[1] = 1;
    bool leaf[500001] = {0}; //if leaf -> false
    vector<int> v;
    int N,a,b;
    long long dis = 0;
    
    cin >> N;
 
    for(int i = 1; i <= N-1; i++){
        cin >> a >> b;
        if(!tr[b]) {tr[b] = a;leaf[a] = true;}
        if(!tr[a]) {tr[a] = b;leaf[b] = true;}
    }
    
    for(int i = 1; i <= N; i++){
        if(!leaf[i]) v.push_back(i);
    }
    
    while(!v.empty()){
        int marker = v.back(); v.pop_back();
        while(marker != 1){
            dis+=1;
            marker = tr[marker];
        }
    }
    
    if(dis%2) cout << "Yes";
    else cout << "No";
}
cs


트리 구현이랑, 트리 탐색(?)에서 좀 막혀서 dfs로 푼 다른 소스보고 참고해서 풀었습니다.


저는 bfs 구현이 더 재미있고 좀 쉽더군요. 재귀함수는 영....


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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> tr[500001];
bool visited[500001];
int layer[500001];
long long ret;
 
void bps(int start, long long dist);
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,a,b;
    
    cin >> N;
    
    for(int i = 1; i <= N-1; i++){
        cin >> a >> b;
        tr[b].push_back(a);
        tr[a].push_back(b);
    }
    
    bps(1,0);
    if(ret%2) cout << "Yes";
    else       cout << "No";
}
 
void bps(int start, long long dist){
    queue<int> q;
    q.push(1); visited[1] = true;
    int layer_chk = 1;
    layer[1] = 1;
    
    while(!q.empty()){
        int tmp = q.front(); q.pop();
        
        if(layer_chk != layer[tmp]){
            dist+=1;
            layer_chk = layer[tmp];
        }
        
        if(tr[tmp].size() == 1 && visited[tr[tmp].back()]){
            ret+=dist;
            continue;
        }
        
        while(!tr[tmp].empty()){
            int v_tmp = tr[tmp].back(); tr[tmp].pop_back();
            
            if(visited[v_tmp]) continue;
            
            q.push(v_tmp);
            visited[v_tmp] = true;
            layer[v_tmp] = layer[tmp] +1;
        }
 
    }
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[재귀] 백준 11578 팀원 모집  (0) 2018.12.27
[etc] 백준 11575 Affine Cipher  (0) 2018.12.24
[etc] 백준 15903 카드 합체 놀이  (0) 2018.12.22
[ect] 백준 15904 UCPC는 무엇의 약자일까?  (0) 2018.12.22
[etc] 백준 15954 인형들  (0) 2018.12.18

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





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    long long arr[1000];
    int n,m;
    long long ret = 0;
    
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> arr[i];
    
    for(int i = 0; i < m; i++){
        sort(arr,arr+n);
        long long tmp = arr[1] + arr[0];
        arr[0] = tmp; arr[1] = tmp;
    }
    
    for(int i = 0; i < n; i++) ret+=arr[i];
    cout << ret;
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[etc] 백준 11575 Affine Cipher  (0) 2018.12.24
[bfs] 백준 15900 나무 탈출  (2) 2018.12.24
[ect] 백준 15904 UCPC는 무엇의 약자일까?  (0) 2018.12.22
[etc] 백준 15954 인형들  (0) 2018.12.18
[dp] 백준 9461 파도반 수열  (0) 2018.12.11

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
 
int main(){
    string s;
    bool chk[4] = {0};
    getline(cin,s);
    
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'U'){
            chk[0] = true;
        }
        if(s[i] == 'C'){
            if(chk[0]) chk[1] = true;
            if(chk[2]) {chk[3] = true; break;}
        }
        if(s[i] == 'P'){
            if(chk[1]) chk[2] = true;
        }
 
    }
    if(chk[3]) cout << "I love UCPC";
    else        cout << "I hate UCPC";
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[bfs] 백준 15900 나무 탈출  (2) 2018.12.24
[etc] 백준 15903 카드 합체 놀이  (0) 2018.12.22
[etc] 백준 15954 인형들  (0) 2018.12.18
[dp] 백준 9461 파도반 수열  (0) 2018.12.11
[etc] 백준 2164 카드2  (0) 2018.12.11

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



이번 문제는 너무 멍청하게 풀었네요. 속도가 많이 느립니다.


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 <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int N, K;
    int doll[500];
    long double ret = 2147483647;
    
    cin >> N >> K;
    
    for(int i = 0; i < N; i++) cin >> doll[i];
 
    for(int i = 0; i < N; i++){
        
        
        for(int k = 0; k + K <= N; k++){
            bool chk = true;
            long double m = 0;
            long double t = 0;
            for(int j = i; j < i+K+k; j++){
                if(i+K+k > N) {chk= false; break;}
                m+=doll[j];
            }
            m /= K+k;
        
        
            for(int j = i; j < i+K+k; j++){
                if(i+K+k > N){chk = false; break;}
                t+=((doll[j]-m)*(doll[j]-m));
            }
            t /=K+k;
        
            if(chk)ret = min(ret,sqrt(t));
        }
    }
    cout << fixed; cout.precision(11);
    cout << ret;
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[etc] 백준 15903 카드 합체 놀이  (0) 2018.12.22
[ect] 백준 15904 UCPC는 무엇의 약자일까?  (0) 2018.12.22
[dp] 백준 9461 파도반 수열  (0) 2018.12.11
[etc] 백준 2164 카드2  (0) 2018.12.11
[스택] 백준 4949 균형잡힌 세상  (0) 2018.12.11

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


그림을 보면 금방 규칙을 찾을 수 있습니다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,T;
    long long dp[100] = {1,1,1,2,2};
    for(int i = 5; i < 100; i++) dp[i] = dp[i-1] + dp[i-5];
    
    cin >> T;
    
    while(T--){
        cin >> n;
        cout << dp[n-1] << endl;
    }
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[ect] 백준 15904 UCPC는 무엇의 약자일까?  (0) 2018.12.22
[etc] 백준 15954 인형들  (0) 2018.12.18
[etc] 백준 2164 카드2  (0) 2018.12.11
[스택] 백준 4949 균형잡힌 세상  (0) 2018.12.11
[etc] 백준 1085 직사각형에서 탈출  (0) 2018.12.11

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


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>
#include <list>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    list<int> card;
    int N;
    
    cin >> N;
    for(int i = 1; i <= N; i++)
        card.push_back(i);
    
    while(1){
        if(card.size() != 1) {
            card.pop_front();
            card.push_back(card.front());
            card.pop_front();
        }
        else break;
    }
    
    cout << card.front();
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[etc] 백준 15954 인형들  (0) 2018.12.18
[dp] 백준 9461 파도반 수열  (0) 2018.12.11
[스택] 백준 4949 균형잡힌 세상  (0) 2018.12.11
[etc] 백준 1085 직사각형에서 탈출  (0) 2018.12.11
[etc] 백준 1436 영화감독 숌  (0) 2018.12.10

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




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
#include <iostream>
#include <stack>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    while(1){
        string s;
        stack<char> st;
        bool chk = true; //yes or no
        
        getline(cin, s);
        
        if(s[0] == '.') break;
        
        int len = s.length();
        
        for(int i = 0; i < len; i++){
            if(s[i] == '(' || s[i] == '[') st.push(s[i]);
            else if(s[i] == ')'){
                if(st.empty() || st.top() == '['){
                    chk = false;
                    break;
                }
                else st.pop();
            }
            else if(s[i] == ']'){
                if(st.empty() || st.top() == '('){
                    chk = false;
                    break;
                }
                else st.pop();
            }
        }
        
        if(chk && st.empty()) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    
}
cs


반응형

'프로그래밍 > 문제풀이' 카테고리의 다른 글

[dp] 백준 9461 파도반 수열  (0) 2018.12.11
[etc] 백준 2164 카드2  (0) 2018.12.11
[etc] 백준 1085 직사각형에서 탈출  (0) 2018.12.11
[etc] 백준 1436 영화감독 숌  (0) 2018.12.10
[etc] 백준 10809 알파벳 찾기  (0) 2018.12.10

+ Recent posts

티스토리툴바