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


이번 건 많이 쉬웠습니다. 딱히 설명 할 것이 없네요.


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 <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int map[101][101] = {0};
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int bfs(int N, int rain);
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    int N,x,y;
    int ret=0, max_height=0;
    cin >> N;
    
    for(int i = 0 ; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> map[i][j];
            max_height = max(max_height, map[i][j]);
        }
    }
    
    for(int i = 0; i <= max_height; i++){
        ret = max(ret,bfs(N, i));
    }
    cout << ret;
    
    
    
}
 
int bfs(int N, int rain){
    bool visited[100][100]= {0};
    int count = 0;
    queue<pair<int,int>> q; //y,x
    
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j <N; j++){
            
            if(!visited[i][j] && rain <= map[i][j]){
                q.push({i,j});
                count +=1;
                visited[i][j] = 1;
                
                while(!q.empty()){
                
                    for(int k=0;k<4;k++){
                        int y = q.front().first+dy[k];
                        int x = q.front().second + dx[k];
                        if(x <0 || x > N-1 || y < 0 || y > N-1) continue;
                        if(!visited[y][x] && rain <= map[y][x]){
                            visited[y][x] = 1; q.push({y,x});
                        }
                    }
                    q.pop();
                    
                }
                
                
            }
            
        }
    }
    
    return count;
}
cs


반응형

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

[dps, dp] 백준 1520 내리막 길  (0) 2018.11.14
[Dp] 백준 11726 2xn타일링  (0) 2018.11.13
[bfs] 백준 1012 유기농 배추  (0) 2018.11.11
백준 3015 오아시스 재결합  (0) 2018.11.10
백준 2294 (동전2)  (0) 2018.11.09


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



bfs는 이번에 푼 문제가 거의 처음이여서 그런지, 실수가 있었습니다.


그냥 if문을 썼어야 됬는데, else if 를 써서 틀렸더라고요. if로 수정하니 잘 됬습니다.






처음엔 이렇게 풀었었습니다.

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 <iostream>
#include <queue>
using namespace std;
bool map[50][50] = {0};
 
void bfs(int height, int width);
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    int T, height, width, N,x,y;
    cin >> T;
    
    for(int i = 0 ; i < T; i++){
        cin >> width >> height;
        cin >> N;
 
        for(int i = 0; i < N; i++){
            cin >> x >> y;
            map[y][x] = 1;
        }
        
        bfs(height, width);
    }
    
    
}
 
void bfs(int height, int width){
 
    int count = 0;
    queue<pair<int,int>> q; //y,x
    
    
    for(int i = 0; i < height; i++){
        for(int j = 0; j < width; j++){
            
            if(map[i][j]){
                q.push({i,j});
                count +=1;
                map[i][j] = 0;
                
                while(!q.empty()){
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();
                    if(y+1 < 50 && map[y+1][x]){
                            map[y+1][x] = 0; q.push({y+1,x});
                    }
                    if(y-1 >= 0 && map[y-1][x]){
                            map[y-1][x] = 0; q.push({y-1,x});
                    }
                    if(x+1 < 50 && map[y][x+1]){
                            map[y][x+1] = 0; q.push({y,x+1});
                    }
                    if(x-1 >= 0 && map[y][x-1]){
                            map[y][x-1] = 0; q.push({y,x-1});
                    }
                }
                
                
            }
            
        }
    }
    
    cout << count << endl;
}
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
59
60
61
62
63
64
65
66
#include <iostream>
#include <queue>
using namespace std;
bool map[50][50] = {0};
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void bfs(int height, int width);
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    int T, height, width, N,x,y;
    cin >> T;
    
    for(int i = 0 ; i < T; i++){
        cin >> width >> height;
        cin >> N;
 
        for(int i = 0; i < N; i++){
            cin >> x >> y;
            map[y][x] = 1;
        }
        
        bfs(height, width);
    }
    
    
}
 
void bfs(int height, int width){
 
    int count = 0;
    queue<pair<int,int>> q; //y,x
    
    
    for(int i = 0; i < height; i++){
        for(int j = 0; j < width; j++){
            
            if(map[i][j]){
                q.push({i,j});
                count +=1;
                map[i][j] = 0;
                
                while(!q.empty()){
                
                    for(int k=0;k<4;k++){
                        int y = q.front().first+dy[k];
                        int x = q.front().second + dx[k];
                        if(x <0 || x >= width || y < 0 || y >= height) continue;
                        if(map[y][x]){
                            map[y][x] = 0; q.push({y,x});
                        }
                    }
                    q.pop();
                    
                }
                
                
            }
            
        }
    }
    
    cout << count << endl;
}
cs

잘 되더라고요.

반응형

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

[Dp] 백준 11726 2xn타일링  (0) 2018.11.13
[bfs] 백준 2468 안전 영역  (0) 2018.11.13
백준 3015 오아시스 재결합  (0) 2018.11.10
백준 2294 (동전2)  (0) 2018.11.09
백준 2293 (동전1)  (0) 2018.11.07

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





키가 같은 경우에서 애 먹었습니다.





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
#include <iostream>
#include <stack>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);    //cin 속도 증가시키기 위해
    stack<pair<int,int>> st;            //first는 키, second는 키가 같은 경우
    int N,tmp, chk;                     //tmp는 키, chk는 키가 같은 경우
    long long count = 0;
    cin >> N;
    
    for(int i = 0; i < N; i++){
        cin >> tmp;
        chk = 1;
        while(!st.empty() && st.top().first <= tmp){
                count += st.top().second;
                if(st.top().first == tmp) chk+= st.top().second;
                st.pop();
        }
        if(!st.empty()) count +=1;;
        
        st.push({tmp,chk});    
    }
    cout << count;
}
cs


반응형

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

[bfs] 백준 2468 안전 영역  (0) 2018.11.13
[bfs] 백준 1012 유기농 배추  (0) 2018.11.11
백준 2294 (동전2)  (0) 2018.11.09
백준 2293 (동전1)  (0) 2018.11.07
백준 2193 (이친수)  (0) 2018.11.06

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


해결 방법 : 동적 계획법




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int dp[10001]={0};
    int coin[101] = {0};
    int N,k;
    cin >> N >> k;
    
    for(int i = 1; i <= N; i++) cin >> coin[i];    
    for(int i = 1; i <=k; i++) dp[i] = 10001;
    
    
    for(int i = 1; i <= N; i++){
        for(int j = coin[i]; j <=k; j++)
            dp[j] = min(dp[j],dp[j-coin[i]] + 1);
    }
    
    dp[k] == 10001 ?cout << -1 : cout << dp[k];
}
cs


반응형

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

[bfs] 백준 1012 유기농 배추  (0) 2018.11.11
백준 3015 오아시스 재결합  (0) 2018.11.10
백준 2293 (동전1)  (0) 2018.11.07
백준 2193 (이친수)  (0) 2018.11.06
백준 10844 (쉬운 계단 수)  (0) 2018.11.06

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


동적계획법 이용.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
 
int main(){
    int dp[10001] = {0};
    int coin[101] = {0};
    int N,k;
    cin >> N >> k;
    
    for(int i = 1; i <= N; i++) cin >> coin[i];
    
    
    dp[0] = 1; //coin[i]로 dp[i] 채우기 위해.
    for(int i = 1; i <= N; i++){
        for(int j = coin[i]; j <=k; j++)
            dp[j] += dp[j-coin[i]];
    }
    
    cout << dp[k];
}
cs


반응형

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

백준 3015 오아시스 재결합  (0) 2018.11.10
백준 2294 (동전2)  (0) 2018.11.09
백준 2193 (이친수)  (0) 2018.11.06
백준 10844 (쉬운 계단 수)  (0) 2018.11.06
백준 2156(포도주 시식)  (0) 2018.11.03

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



점화식 dp[i] = dp[i-1] + dp[i-2] 이용


첫 숫자는 무조건 10이다. 

10 뒤로 오는 숫자가 문제인데,

만약 1이 올 경우는, dp[i-2]와 같다.

만약 0이 올 경우는, dp[i-1]의 맨 앞 자리 숫자를 제외한 모두와 같다.


ex)

2: 10

3: 101 100

4 : 1010 1001 1000

5 : 10010 10001 10000 10101 10100


1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
 
int main(){
    long dp[91];
    int N;
    cin >> N;
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i <= N; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[N];
}
cs


반응형

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

백준 2294 (동전2)  (0) 2018.11.09
백준 2293 (동전1)  (0) 2018.11.07
백준 10844 (쉬운 계단 수)  (0) 2018.11.06
백준 2156(포도주 시식)  (0) 2018.11.03
백준 1107 (리모컨)  (0) 2018.11.03

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


점화식 dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1] 이용


여기서 N 은 자릿수, i는 끝나는 수


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
#include <iostream>
#define mod 1000000000
using namespace std;
 
int main(){
    int dp[101][10] = {};
    for(int i = 0; i < 10; i++){
        dp[1][i] = 1;
    }
    
    int N;
    cin >> N;
    
    for(int i = 2; i <=N; i++){
        for(int j = 0; j < 10; j++){
            if(j == 0) dp[i][j] = dp[i-1][1];
            else if(j == 9) dp[i][j] = dp[i-1][8];
            else dp[i][j] = dp[i-1][j-1]+ dp[i-1][j+1]; 
            dp[i][j] %=mod;
        }
    }
    
    int sum = 0;
    
    for(int i = 1; i<10; i++){
        sum=(sum+dp[N][i]) %mod;
    }
    cout << sum%mod;
}
cs


2. 재귀

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
#include <iostream>
#define mod 1000000000
using namespace std;
 
int dp[101][10]={0};
 
int step(int N,int x);
 
int main(){
    int N;
    int sum = 0;
    cin >> N;
    
    for(int i =0;i<10;i++) sum = (sum+step(N,i)) % mod; 
    
    cout << sum;
    
}
 
int step(int N,int x){
    if(N==1) return x == 0 ? 0:1;
    int& ref = dp[N][x];
    if(ref) return ref;
    if(x == 0) return ref = step(N-1,1)%mod;
    if(x == 9) return ref = step(N-1,8)%mod;
    return ref = (step(N-1,x-1) + step(N-1,x+1)) %mod;
    
}
cs


반응형

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

백준 2293 (동전1)  (0) 2018.11.07
백준 2193 (이친수)  (0) 2018.11.06
백준 2156(포도주 시식)  (0) 2018.11.03
백준 1107 (리모컨)  (0) 2018.11.03
백준 1652 (누울 자리를 찾아라)  (0) 2018.11.03
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int n;
    int f[100001];
    int dp[100001];
    cin >> n;
    for(int i = 1; i<= n;i++) cin >> f[i];
    dp[1] = f[1];
    dp[2] = f[1]+f[2];
    for(int i = 3; i <=n; i++){
        dp[i]= max(dp[i-2]+f[i],dp[i-3]+f[i-1]+f[i]);
        dp[i] = max(dp[i],dp[i-1]);
    }
    cout << dp[n];
    
}
cs



점화식 : 

i 번째를 마시지 않은 경우 : dp[i] = dp[i-1]

i 번째를 마시고, 그 전 것도 마신 경우 : dp[i] = dp[i-3]+f[i-1]+f[i]

i 번째를 마시고, 그 다음 것을 마실 경우 :dp[i] = dp[i-2] + f[i]      

반응형

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

백준 2193 (이친수)  (0) 2018.11.06
백준 10844 (쉬운 계단 수)  (0) 2018.11.06
백준 1107 (리모컨)  (0) 2018.11.03
백준 1652 (누울 자리를 찾아라)  (0) 2018.11.03
백준 9095 (1,2,3 더하기)  (0) 2018.10.31
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
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
bool broken[10] = {false,};
int len_chk(int N); //길이와 버튼 누를수 있는 지 확인
 
int main(){
    int N, M,d;
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int tmp; cin >> tmp;
        broken[tmp] = true;
    }
    d = abs(100-N);
    
    for(int i = 0; i < 1000001; i++){
        int length = len_chk(i);
        if(length){
            d = min(d, length+abs(i-N));
        }
    }
    cout << d;
}
 
int len_chk(int N){
    int length = 0;
    if(N==0) return broken[0] ? 0:1;
    while(N){
        length++;
        if(broken[N%10]) return 0;
        N/=10;
    }
    return length;
}
cs


반응형

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

백준 10844 (쉬운 계단 수)  (0) 2018.11.06
백준 2156(포도주 시식)  (0) 2018.11.03
백준 1652 (누울 자리를 찾아라)  (0) 2018.11.03
백준 9095 (1,2,3 더하기)  (0) 2018.10.31
백준 1463(1로 만들기)  (0) 2018.10.29


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




이번 문제는 생각보다 쉬웠습니다.

최대한 속도를 빠르게 해보려고 시도했는데, 좀 애매하네요.




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
#include <iostream>
using namespace std;
int main(){
    int N, x_chk=0, x_count = 0, y_count = 0;
    int y_chk[100] = {0,};//0 장애물, 1 누울 자리, 2 이미 누운곳
    char tmp;
    cin >> N;
    
    for(int i = 0; i < N; i++){
        
        for(int j = 0; j <N; j++){
            cin >> tmp;
            if(tmp == 'X'){
                y_chk[j] = 0;
                x_chk=0;
            }
            else{
                if(y_chk[j] == 1){
                    y_chk[j] =2;
                    y_count +=1;
                }
                else if(y_chk[j] == 0)y_chk[j] =1;
                
                if(x_chk == 1){
                    x_chk = 2;
                    x_count +=1;
                }
                else if(x_chk == 0)x_chk = 1;
            }
        }
        x_chk = 0;
    }
    cout << x_count <<' ' << y_count;
    
}
cs


반응형

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

백준 2156(포도주 시식)  (0) 2018.11.03
백준 1107 (리모컨)  (0) 2018.11.03
백준 9095 (1,2,3 더하기)  (0) 2018.10.31
백준 1463(1로 만들기)  (0) 2018.10.29
백준 3986(좋은 단어)  (0) 2018.10.20

+ Recent posts

티스토리툴바