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


처음에 토마토가 들어가 있는 좌표를 queue에 push합니다.


그리고 queue에 있는 것을 하나 씩 꺼내서 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
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <queue>
using namespace std;
 
int map[100][100][100];
int h,n,m;
 
bool chk(){
    for(int i = 0; i < h; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                if(map[i][j][k] == 0) return true;
            }
        }
    }
    return false;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    
    bool visited[100][100][100] = {0};
    int dz[6] = {1,-1,0,0,0,0};
    int dy[6] = {0,0,1,-1,0,0};
    int dx[6] = {0,0,0,0,1,-1};
    queue<pair<int,pair<int,int> > > q;
    int day = -1;
    
    cin >> m >> n >> h;
    
    for(int i = 0; i < h; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                cin >> map[i][j][k];
                if(map[i][j][k] == 1){
                    q.push({i,{j,k}});
                    visited[i][j][k] = true;
                }
            }
        }
    }
    
    if(!chk()){
        cout << 0;
        return 0;
    }
    
    while(!q.empty()){
        int size = q.size();
        day+=1;
        
        for(int i = 0; i < size; i++){
            int x = q.front().second.second, y = q.front().second.first, z = q.front().first;
            q.pop();
            for(int j = 0; j < 6; j++){
                int xx = x + dx[j], yy = y + dy[j], zz = z + dz[j];
                if(xx >= m || yy >= n || zz >= h || xx < 0 || yy < 0 || zz < 0) continue;
                if(visited[zz][yy][xx] || map[zz][yy][xx] == -1) continue;
                visited[zz][yy][xx] = true;
                map[zz][yy][xx] = 1;
                q.push({zz,{yy,xx}});
            }
        }
        
    }
    
    if(chk())    cout << -1;
    else cout << day;
    
}
cs


반응형

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

[bfs, dfs] 백준 2667 단지번호붙이기  (0) 2019.03.24
[dfs] 백준 2606 바이러스  (0) 2019.03.22
[bfs] 라비다 1052 maze problem  (0) 2019.03.18
[dp] 백준 1495 기타리스트  (0) 2019.02.20
[dp] 백준 1309 동물원  (0) 2019.02.02

https://judge.lavida.us/problem.php?id=1052


아주대 A.N.S.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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <queue>
using namespace std;
 
 
int main(){
    ios_base::sync_with_stdio(false);
    int t;
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    
    cin >> t;
    
    while(t--){
        char map[100][100];
        int n,m;
        pair<int,int> start;
        cin >> n >> m;
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> map[i][j];
                if(map[i][j] == 'S')  start = {i,j};
            }
        }
        
        queue<pair<int,int> > q;
        bool visited[100][100] = {0};
        bool check_goal = 0;
        int count = 0;
        q.push(start);
        
        while(!q.empty() && !check_goal){
            int size = q.size();
            count++;
            
            for(int i = 0; i < size; i++){
                int x = q.front().second, y = q.front().first;
                q.pop();
                
                for(int i= 0; i  < 4; i++){
                    int xx = x  + dx[i], yy = y+dy[i];
                    
                    if(xx < 0 || yy < 0 || xx >= m || yy >= n) continue;
                    if(visited[yy][xx] || map[yy][xx] == '#') continue;
                    if(map[yy][xx] == 'E'){
                        check_goal = true;
                        break;
                    }
                    q.push({yy,xx});
                    visited[yy][xx] = true;
                }
            }
        }
        if(check_goal) cout << count << endl;
        else          cout << -1 << endl;
    }    
}
cs


간단히 bfs를 이용해 최단경로 찾는 문제입니다.

반응형

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

[dfs] 백준 2606 바이러스  (0) 2019.03.22
[bfs] 백준 7569 토마토  (0) 2019.03.22
[dp] 백준 1495 기타리스트  (0) 2019.02.20
[dp] 백준 1309 동물원  (0) 2019.02.02
[dp] 백준 2579 계단오르기  (0) 2019.02.02

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


다이나믹 프로그래밍을 이용헤서 풀었습니다.


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
#include <iostream>
using namespace std;
 
int main() {
    int n, s, m;
    bool dp[101][10001] = { {0,}, };
    int v[101];
    int ret = -1;
 
    cin >> n >> s >> m;
 
    for (int i = 1; i <= n; i++) cin >> v[i];
 
    if (s - v[1] >= 0) dp[1][s-v[1]] = true;
    if (s + v[1] <= m) dp[1][s+v[1]] = true;
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (dp[i - 1][j]) {
                if (j - v[i] >= 0) dp[i][j - v[i]] = true;
                if (j + v[i] <= m) dp[i][j + v[i]] = true;
            }
        }
    }
    
    for (int i = 0; i <= m; i++)
        if (dp[n][i]) ret = i;
    
    cout << ret;
 
}
cs


반응형

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

[bfs] 백준 7569 토마토  (0) 2019.03.22
[bfs] 라비다 1052 maze problem  (0) 2019.03.18
[dp] 백준 1309 동물원  (0) 2019.02.02
[dp] 백준 2579 계단오르기  (0) 2019.02.02
[etc] 백준 10757 큰 수 A+B  (0) 2019.01.29

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
 
int main(){
    int n;
    int dp[100001];
    
    cin >> n;
    
    dp[0] = 1; dp[1] = 3;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1]*2 + dp[i-2];
        dp[i]%=9901;
    }
    cout << dp[n];
}
cs


반응형

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

[bfs] 라비다 1052 maze problem  (0) 2019.03.18
[dp] 백준 1495 기타리스트  (0) 2019.02.20
[dp] 백준 2579 계단오르기  (0) 2019.02.02
[etc] 백준 10757 큰 수 A+B  (0) 2019.01.29
[etc] 백준 16678 모독  (0) 2019.01.27

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



마지막을 생각하면 편합니다.


마지막을 밟고, 그 전 칸을 밟은 경우 : dp[n] = dp[n-3] + arr[n] + arr[n-1]

마지막을 밟고, 그 전 전 칸을 밟은 경우: dp[n] = dp[n-2]+arr[n]


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(){
    int n,tmp;
    int dp[301] = {0};
    int arr[301];
    
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    
    dp[1] = arr[1];
    dp[2] = arr[1]+arr[2];
    dp[3] = max(arr[1]+arr[3], arr[2]+arr[3]);
    
    for(int i = 4; i <= n; i++)
        dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i]+arr[i-1]);
    
    cout << dp[n];
}
cs


반응형

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

[dp] 백준 1495 기타리스트  (0) 2019.02.20
[dp] 백준 1309 동물원  (0) 2019.02.02
[etc] 백준 10757 큰 수 A+B  (0) 2019.01.29
[etc] 백준 16678 모독  (0) 2019.01.27
[etc] 백준 16676 근우의 다이어리 꾸미기  (0) 2019.01.24

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


구현을 쉽게 하기 위해서 reverse iterator를 사용했습니다.



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
#include <iostream>
using namespace std;
 
int main(){
    string s1, s2,ret;
    int num=0;
    
    cin >> s1 >> s2;
    if(s1.size() > s2.size()){
        string tmp = s2;
        s2 = s1;
        s1 = tmp;
    }
    
    auto it1 = s1.rbegin();
    auto it2 = s2.rbegin();
    
    for(;it1 != s1.rend(); it1++, it2++){
        int sum = *(it1)-48+*(it2)-48+num;
        ret = char(sum%10+48) + ret;
        num = sum/10;
    }
    for(;it2!=s2.rend();it2++){
        int sum = *(it2)-48 + num;
        ret = char(sum%10+48) + ret;
        num = sum/10;
    }
    if(num > 0)
        ret = char(num+48) + ret;
    
    cout << ret;
}
cs


반응형

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

[dp] 백준 1309 동물원  (0) 2019.02.02
[dp] 백준 2579 계단오르기  (0) 2019.02.02
[etc] 백준 16678 모독  (0) 2019.01.27
[etc] 백준 16676 근우의 다이어리 꾸미기  (0) 2019.01.24
[etc] 백준 16674 2018년을 되돌아보며  (0) 2019.01.22

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


처음 시행 될 때를 생각해야 되기 때문에 t는 1.


arr[i]가 t보다 크거나 같으면, 그 수 만큼 해커가 있어야 다시 시행 가능.


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(){
    int arr[100000];
    int n,t=1;
    long ans = 0;
    
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr,arr+n);
    
    for(int i = 0; i < n; i++){
        if(arr[i] >= t){
            ans+=arr[i]-t;
            t++;
        }
    }
    cout << ans;
}
cs


반응형

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

[dp] 백준 2579 계단오르기  (0) 2019.02.02
[etc] 백준 10757 큰 수 A+B  (0) 2019.01.29
[etc] 백준 16676 근우의 다이어리 꾸미기  (0) 2019.01.24
[etc] 백준 16674 2018년을 되돌아보며  (0) 2019.01.22
[bfs] 백준 16569 화산쇄설류  (0) 2019.01.17

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



처음 제출 했을 때, 0인 경우를 생각 못해서 틀렸습니다.


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 <cstdlib>
using namespace std;
 
int main(){
    int n,chk_n;
    string s_chk_n;
    
    cin >> n;
    
    string s = to_string(n);
    
    
    int size = s.size();
    for(int i = 0; i < size; i++)
        s_chk_n+='1';
    chk_n = atoi(s_chk_n.c_str());    
 
    if(n>=chk_n) cout << size;
    else if(n == 0) cout << 1;
    else         cout << size-1;
}
cs


반응형

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

[etc] 백준 10757 큰 수 A+B  (0) 2019.01.29
[etc] 백준 16678 모독  (0) 2019.01.27
[etc] 백준 16674 2018년을 되돌아보며  (0) 2019.01.22
[bfs] 백준 16569 화산쇄설류  (0) 2019.01.17
[etc] 백준 13118 뉴턴과 사과  (0) 2019.01.15

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


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
#include <iostream>
using namespace std;
 
int main(){
    int cnt[5] = {0};
    bool chk[4] = {0};
    string s;
    cin >> s;
    
    int size = s.size();
    for(int i = 0; i  < size; i++){
        switch(s[i]){
            case '2':
                cnt[0] +=1;
                break;
            case '0':
                cnt[1] +=1;
                break;
            case '1':
                cnt[2] +=1;
                break;
            case '8':
                cnt[3]+=1;
                break;
            default:
                cnt[4] +=1;
        }
    }
    
    if(cnt[4])chk[3] = true;
    else if(((cnt[0] == cnt[1]) && cnt[1] == cnt[2]) && cnt[2] == cnt[3])    chk[2] = true;
    else if(cnt[0] >=1 && cnt[1] >=1 &&cnt[2] >=1 &&cnt[3] >=1 )   chk[1] = true;
    else if(cnt[0] >=1 || cnt[1] >=1 || cnt[2] >=1 || cnt[3] >=1 ) chk[0] = true;
    
    
 
    
    for(int i = 3; i >= 0; i--){
        if(chk[i]){
            if(i == 3) cout << 0;
            else if(i == 2) cout << 8;
            else cout << i+1;
            break;
        }
    }
}
cs


반응형

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

[etc] 백준 16678 모독  (0) 2019.01.27
[etc] 백준 16676 근우의 다이어리 꾸미기  (0) 2019.01.24
[bfs] 백준 16569 화산쇄설류  (0) 2019.01.17
[etc] 백준 13118 뉴턴과 사과  (0) 2019.01.15
[dp, bfs] 백준 16568 엔비스카의 영혼  (0) 2019.01.05

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


생각보다 많이 힘들었습니다. 


화산재에 덮이는 시간을 저장하는 배열을 하나 더 만들어서 풀었습니다.


처음에 화산의 위치를 재상이가 지나갈 수 있게 만들어서 틀렸었습니다.


그래서 40번 줄을 수정해서 화산이 있는 곳의 시간은 0으로 저장하니 맞았습니다.


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
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int m,n,v,u_x,u_y;
    int map[100][100];
    int t_map[100][100];        //화산재에 덮이는 시간
    pair<int,pair<int,int>> p[10000];
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++)
            t_map[i][j] =10000;
    }
    
    cin >> m >> n >> v >> u_x >> u_y;
    
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++)
            cin >> map[i][j];
    }
    
    for(int i = 0; i < v; i++){
        cin >> p[i].second.first >> p[i].second.second >> p[i].first ;
    }
 
    //화산재에 덮이는 시간들 저장.
    
    for(int i = 0; i < v; i++){
        
        bool visited[100][100] = {0};
        queue<pair<int,int>> q;
        int t = p[i].first+1;
        
        q.push({p[i].second.second-1, p[i].second.first-1});
        t_map[q.front().second][q.front().first] = 0;
        while(!q.empty()){
            int size = q.size();
            
            for(int k = 0; k < size; k++){
                int x = q.front().first; int y = q.front().second;
                q.pop();
                
                for(int j = 0; j < 4; j++){
                    int tx = x+dx[j]; int ty= y+dy[j];
                    if(visited[ty][tx]) continue;
                    if(ty >= m || tx >= n || ty < 0 || tx < 0) continue;
                    t_map[ty][tx] = min(t_map[ty][tx],t);
                    visited[ty][tx] = true;
                    q.push({tx,ty});
                }
            }
            t+=1;
        }
    }
    
    
    int t = 1;
    int height,max_t = 0;
    bool visited[100][100] = {};
    queue<pair<int,int>> q;
    //처음 위치의 높이를 height에 저장.
    q.push({u_y-1,u_x-1});
    height = map[q.front().second][q.front().first];
    
    while(!q.empty()){
        int size = q.size();
 
        for(int i = 0; i < size; i++){
            int x = q.front().first; int y = q.front().second;
            q.pop();
            
            for(int j = 0; j < 4; j++){
                int tx = x+dx[j]; int ty = y+dy[j];
                
                if(visited[ty][tx]) continue;
                if(ty >= m || tx >= n || ty < 0 || tx < 0) continue;
                if(t_map[ty][tx] <= t){
                    visited[ty][tx] = 1;
                    continue;
                }
                if(height == map[ty][tx])
                    max_t = min(max_t,t);
                if(height < map[ty][tx]){
                    max_t = t;
                    height = map[ty][tx];
                }
                visited[ty][tx] = true;
                q.push({tx,ty});
            }
        }
        t+=1;
    }
    
    cout << height <<' ' << max_t;
}
cs


반응형

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

[etc] 백준 16676 근우의 다이어리 꾸미기  (0) 2019.01.24
[etc] 백준 16674 2018년을 되돌아보며  (0) 2019.01.22
[etc] 백준 13118 뉴턴과 사과  (0) 2019.01.15
[dp, bfs] 백준 16568 엔비스카의 영혼  (0) 2019.01.05
[슬라이딩 윈도우] 백준 15831 준표의 조약돌  (0) 2018.12.31

+ Recent posts

티스토리툴바