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


파란색이랑 빨간색 동시에 움직이게 하는 거에 막혀서...


솔직히 이번 문제는 다른 분의 블로그를 보고 풀었습니다.



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
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
bool visited[10][10][10][10];
char map[10][10];
queue<pair<pair<int,int>,pair<int,int>>> q;
int bfs();
 
int main(){
    int n,m;
    int bx,by,rx,ry;
    
    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] == 'R') {rx = j; ry = i;}
            else if(map[i][j] == 'B'){bx = j; by = i;}
        }
    }
    q.push({{rx,ry},{bx,by}});
    visited[rx][ry][bx][by] = 1;
    
    cout << bfs();
}
 
int bfs(){
    int cnt = 0;
    
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            int rx = q.front().first.first;
            int ry = q.front().first.second;
            int bx = q.front().second.first;
            int by = q.front().second.second;
            q.pop();
            
            if(map[ry][rx] == 'O' && map[by][bx] != map[ry][rx]) return cnt;
            for(int j = 0; j < 4; j++){
                int rxt = rx, ryt = ry, bxt = bx, byt = by;
                while(map[ryt+dy[j]][rxt+dx[j]] != '#' && map[ryt][rxt] != 'O'){    
                    rxt += dx[j]; ryt += dy[j];
                }
                while(map[byt+dy[j]][bxt+dx[j]] != '#' && map[byt][bxt] != 'O'){
                    bxt += dx[j]; byt +=dy[j];
                }
                if(bxt == rxt && byt == ryt){
                    if(map[ryt][rxt] =='O') continue;
                    if(abs(rxt-rx)+abs(ryt-ry) > abs(byt-by)+abs(bxt-bx)){
                        ryt-=dy[j]; rxt-=dx[j];
                    }
                    else{
                        bxt-=dx[j]; byt-=dy[j];
                    }
                }
                if(visited[rxt][ryt][bxt][byt])continue;
                q.push({{rxt,ryt},{bxt,byt}});
                visited[rxt][ryt][bxt][byt]=1;
            }
            
        }
        if(cnt == 10) return -1;
        cnt ++;
    }
    return -1;
}
cs


반응형

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

[etc] 백준 1049 기타줄  (0) 2018.12.07
[etc] 백준 1931 회의실 배정  (0) 2018.12.07
[etc] 백준 13456 시험 감독  (0) 2018.11.26
[bfs] 백준 16234 인구 이동  (0) 2018.11.24
[bfs] 백준 3055 탈출  (0) 2018.11.23

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int N,B,C;
    long long sum = 0;
    int A[1000000];
    
    cin >> N;
    for(int i = 0; i < N; i++) cin >> A[i];
    cin >> B >> C;
    
    for(int i = 0; i < N; i++){
        sum += 1;
        A[i] -= B;
        if(A[i] < 0) continue;
        sum += A[i]/C;
        if(A[i]%C) sum +=1;
    }
    cout << sum;
}
cs
반응형

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

[etc] 백준 1931 회의실 배정  (0) 2018.12.07
[bfs] 백준 13460 구슬 탈출2  (0) 2018.11.28
[bfs] 백준 16234 인구 이동  (0) 2018.11.24
[bfs] 백준 3055 탈출  (0) 2018.11.23
[bfs] 백준 5014 스타트링크  (0) 2018.11.21

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


삼성 SW 역량 테스트 기출 문제 라는 문제집에 있는 문제입니다.


이 문제도 생각보다 많이 쉬웠습니다. 


우선 map에 있는 연합을 하나 찾고, 그 연합의 값을 전부 바꿉니다. 이때, visited가 큰 역할을 합니다. 바꾼 연합을 또 바꾸는 일이 사라지거든요. 이 과정을 계속 반복하니 풀렸습니다.


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
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int map[50][50];
    int N,L,R;
    bool chk = true;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    int ans = 0;
    queue<pair<int,int>> q;      //bfs용
    queue<pair<int,int>> pos; //연합의 좌표를 저장
    
    cin >> N >> L >> R;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++)
            cin >> map[i][j];
    }
    
    while(chk){
        bool visited[50][50] = {};
        chk = false; ans+=1;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(visited[i][j]) continue;
                int sum = map[i][j];
                q.push({j,i});
                pos.push({j,i});
                visited[i][j] = 1;
                
                while(!q.empty()){
                    int x_tmp = q.front().first;
                    int y_tmp = q.front().second;
                    q.pop();
                    
                    for(int k = 0; k < 4; k++){
                        int x = x_tmp+dx[k];
                        int y = y_tmp+dy[k];
                        if(x < 0 || y < 0 || x >= N || y >= N || visited[y][x] || abs(map[y_tmp][x_tmp]-map[y][x]) < L ||abs(map[y_tmp][x_tmp]-map[y][x])>R)
                            continue;
                        chk = true;
                        q.push({x,y});
                        pos.push({x,y});
                        sum+=map[y][x];
                        visited[y][x] = 1;
                    }
                
                }
            
                
                int avr = sum/pos.size();
 
                while(!pos.empty()){
                    map[pos.front().second][pos.front().first] = avr;
                    pos.pop();
                }
            }
        }
        
    }
    cout << ans-1;
}
cs


반응형

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

[bfs] 백준 13460 구슬 탈출2  (0) 2018.11.28
[etc] 백준 13456 시험 감독  (0) 2018.11.26
[bfs] 백준 3055 탈출  (0) 2018.11.23
[bfs] 백준 5014 스타트링크  (0) 2018.11.21
[etc] 백준 1350 진짜 공간  (0) 2018.11.21

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


매분이 지날 때 마다 물을 확장 시킵니다.

그리고 고슴도치가 이동합니다.


이런 식으로 해서 풀었습니다. 좀 난잡하네요. visited가 없어도 될 것 같기도 한데...


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
#include <iostream>
#include <queue>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    pair<int,int> ans;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    int min = 0;
    char map[51][51];
    bool visited[51][51] = {};
    int R,C;
    queue<pair<int,int>> S; //x,y
    queue<pair<int,int>> water;
    cin >> R >> C;
    
    for(int i = 0; i < R; i++){
        for(int j = 0; j <C; j++){
            cin >> map[i][j];
            if(map[i][j] == 'S') {S.push({j,i}); visited[i][j] = 1;}
            else if(map[i][j] == '*') water.push({j,i});
            else if(map[i][j] == 'D') ans = {j,i};
        }
    }
    
    while(!S.empty()){
        if(visited[ans.second][ans.first]) break;
        
        min+=1;
        
        pair<int,int> tmp;
        int water_size = water.size();
        for(int i = 0; i < water_size; i++){
            tmp = water.front();
            water.pop();
            for(int j = 0; j < 4; j++){
                int x = tmp.first+dx[j];
                int y = tmp.second+dy[j];
                if(y >= R || x >= C || y <0 || x < 0 || map[y][x] != '.') 
                    continue;
                water.push({x,y}); map[y][x] = '*';
            }
        }
        
        int S_size = S.size();
        for(int i = 0; i < S_size; i++){
            if(visited[ans.second][ans.first]) break;
            tmp = S.front();
            S.pop();
            for(int j = 0; j < 4; j++){
                int x = tmp.first+dx[j];
                int y = tmp.second+dy[j];
                
                if(y >= R || x >= C || y <0 || x < 0 || visited[y][x])
                    continue;
                
                if(map[y][x] != '.'){
                    if(map[y][x] == 'D') {
                        visited[y][x] = 1; 
                        break;
                    }
                    continue;
                }
                
                visited[y][x] = 1;
                S.push({x,y});
            }
        }
    }
    
    
    if(visited[ans.second][ans.first]) cout << min;
    else cout << "KAKTUS";
    
}
cs


반응형

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

[etc] 백준 13456 시험 감독  (0) 2018.11.26
[bfs] 백준 16234 인구 이동  (0) 2018.11.24
[bfs] 백준 5014 스타트링크  (0) 2018.11.21
[etc] 백준 1350 진짜 공간  (0) 2018.11.21
[stack] 백준 2841 외계인의 기타 연주  (0) 2018.11.19

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



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 <iostream>
#include <queue>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int f,s,g,u,d;
    int cnt[1000001] = {};
    
    queue<int> q;
    
    cin >> f >> s >> g >> u >> d;
    
    q.push(s);
    cnt[s] = 1; // 방문한지 안 한지 구분 위해.
    
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(cur == g) break;
        int df[2] = {cur + u, cur -d};
        
        for(int i = 0; i < 2; i++){
            if(df[i]<1 || df[i] > f || cnt[df[i]]) continue;
            cnt[df[i]] = cnt[cur] +1;
            q.push(df[i]);
        }
    }
    
    if(cnt[g]) cout << cnt[g]-1; //처음 시작을 1로 초기화해서.
    else cout << "use the stairs";
    
}
cs


반응형

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

[bfs] 백준 16234 인구 이동  (0) 2018.11.24
[bfs] 백준 3055 탈출  (0) 2018.11.23
[etc] 백준 1350 진짜 공간  (0) 2018.11.21
[stack] 백준 2841 외계인의 기타 연주  (0) 2018.11.19
[dp] 백준 9465 스티커  (0) 2018.11.19

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



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(){
    long long space = 0;
    int f[1000];
    int N, cl;
    
    cin >> N;
    
    for(int i = 0; i < N; i++){
        cin >> f[i];
    }
    cin >> cl;
    for(int i = 0; i < N; i++){
        space += f[i]%cl ? (f[i]/cl)*cl + cl : (f[i]/cl)*cl;
    }
    cout << space;
}
cs

이번 건 쉬웠습니다.

반응형

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

[bfs] 백준 3055 탈출  (0) 2018.11.23
[bfs] 백준 5014 스타트링크  (0) 2018.11.21
[stack] 백준 2841 외계인의 기타 연주  (0) 2018.11.19
[dp] 백준 9465 스티커  (0) 2018.11.19
[dps, dp] 백준 1520 내리막 길  (0) 2018.11.14

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


스택을 이용해서 풀었습니다.


만약에 입력된 플랫보다 큰 값이 있으면 계속 pop 합니다.

플랫보다 작은 값이 있으면 입력된 플랫을 push합니다.

같으면 아무것도 안합니다.


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>
#include <stack>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int p, n;
    int count = 0, note, flat;
    stack<int> st[7];
    
    cin >> n >> p;
        
    for(int i = 0; i < n; i++){
        cin >> note >> flat;
        while(!st[note].empty()){
            if(st[note].top() == flat) break;
            else if(st[note].top() > flat){
                st[note].pop(); count +=1;
            }
            else{
                st[note].push(flat); count+=1;
            }
            
        }
        if(st[note].empty()){
            count +=1; st[note].push(flat);
        }
        
        
    }
    cout << count;
}
cs


반응형

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

[bfs] 백준 5014 스타트링크  (0) 2018.11.21
[etc] 백준 1350 진짜 공간  (0) 2018.11.21
[dp] 백준 9465 스티커  (0) 2018.11.19
[dps, dp] 백준 1520 내리막 길  (0) 2018.11.14
[Dp] 백준 11726 2xn타일링  (0) 2018.11.13

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





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>
#include <algorithm>
using namespace std;
 
int main(){
    int T, n;
    int map[2][100001];
    ios_base::sync_with_stdio(false);
    
    cin >> T;
    
    for(int i = 0; i < T; i++){
        int mem[2][100001] = {0,};
        cin >> n;
        for(int j = 0; j < 2;j++){
            for(int k = 1; k <=n; k++){
                cin >> map[j][k];
            }
        }
        
        mem[0][1] = map[0][1];
        mem[1][1] = map[1][1];
        
        for(int j =2; j <= n ; j++){
            mem[0][j] = max(mem[1][j-1], mem[1][j-2]) + map[0][j];
            mem[1][j] = max(mem[0][j-1], mem[0][j-2]) + map[1][j];
        }
        
        cout <<  max(mem[0][n], mem[1][n]) << endl;
    }
    
}
cs


반응형

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

[etc] 백준 1350 진짜 공간  (0) 2018.11.21
[stack] 백준 2841 외계인의 기타 연주  (0) 2018.11.19
[dps, dp] 백준 1520 내리막 길  (0) 2018.11.14
[Dp] 백준 11726 2xn타일링  (0) 2018.11.13
[bfs] 백준 2468 안전 영역  (0) 2018.11.13

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


처음에 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
#include <iostream>
#include <queue>
using namespace std;
 
int map[501][501] = {0};
int mem[501][501] = {0};
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
 
 
int M, N; //세로, 가로
 
 
int dfs(int x, int y);
 
int main(){
    ios_base::sync_with_stdio(false);
    mem[1][1] = 1;
    cin >> M >> N;
    
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            cin >> map[i][j];
            mem[i][j] = -1;
        }
    }
    
    cout << dfs(1,1);
    
}
 
int dfs(int x, int y){
    
    if(mem[y][x] != -1) return mem[y][x];
    if(x==N && y == M) return 1;
    
    mem[y][x] = 0;
    for(int i = 0; i < 4; i++){
        int nextx = x + dx[i];int nexty = y + dy[i];
        if(nextx>0 && nextx <= N && nexty > 0 && nexty <= M && map[nexty][nextx] <map[y][x])
            mem[y][x] += dfs(nextx,nexty);
    }
    
    return mem[y][x];
}
cs

1520

반응형

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

[stack] 백준 2841 외계인의 기타 연주  (0) 2018.11.19
[dp] 백준 9465 스티커  (0) 2018.11.19
[Dp] 백준 11726 2xn타일링  (0) 2018.11.13
[bfs] 백준 2468 안전 영역  (0) 2018.11.13
[bfs] 백준 1012 유기농 배추  (0) 2018.11.11

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



타일 2개가 가로로 있는 경우, 세로로 한 개 있는 경우 구하면 됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int mem[10001];
    int n;
    
    cin >> n;
    mem[1] = 1;
    mem[2]= 2;
    for(int i = 3; i <= n; i++){
        mem[i] =  (mem[i-1]+mem[i-2])%10007;
    }
    
    cout << mem[n];
}
cs


반응형

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

[dp] 백준 9465 스티커  (0) 2018.11.19
[dps, dp] 백준 1520 내리막 길  (0) 2018.11.14
[bfs] 백준 2468 안전 영역  (0) 2018.11.13
[bfs] 백준 1012 유기농 배추  (0) 2018.11.11
백준 3015 오아시스 재결합  (0) 2018.11.10

+ Recent posts

티스토리툴바