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

github : https://github.com/junho0956/Algorithm/blob/master/1806/1806/%EC%86%8C%EC%8A%A4.cpp

 

저만 이 문제에 낚인걸까요

"만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다."

이 문구에서 일단 합 이상에 대한 최소 길이를 알고 있더라도 정확한 합을 못만들면 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[100001];
int N, M, ans = 100001;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    int left = 0, right = 0;
    int sum = 0;
    bool temp = false;
    while (left <= right && left < N && right <= N) {
        /*if (sum == M) temp = true;*/
        if (sum >= M)
            temp = true, ans = min(ans, right-left), sum -= arr[left++];
        else sum += arr[right++];
    }
    if (temp) cout << ans;
    else cout << 0;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1261번 알고스팟  (0) 2020.01.31
BOJ 1644번 소수의 연속합  (0) 2020.01.31
BOJ 2003번 수들의 합2  (0) 2020.01.31
BOJ 1987번 알파벳  (0) 2020.01.31
BOJ 2580번 스도쿠  (0) 2020.01.31

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

github : https://github.com/junho0956/Algorithm/blob/master/2003/2003/2003.cpp

 

2개의 인덱스를 가지고 좌+1우+1로 왔다갔다 하면서 문제를 해결해주시면 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
int arr[10001];
int N, M, ans;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    int left = 0, right = 0;
    int sum = 0;
    while (left <= right && left < N && right <= N) {
        if (sum == M) ans++;
        if (sum >= M) sum -= arr[left++];
        else sum += arr[right++];
    }
 
    cout << ans;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1644번 소수의 연속합  (0) 2020.01.31
BOJ 1806번 부분합  (0) 2020.01.31
BOJ 1987번 알파벳  (0) 2020.01.31
BOJ 2580번 스도쿠  (0) 2020.01.31
BOJ 2661번 좋은수열  (0) 2020.01.31

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

github : https://github.com/junho0956/Algorithm/blob/master/1987/1987/%EC%86%8C%EC%8A%A4.cpp

 

DFS 를 이용한 백트래킹의 기본문제였습니다.

 

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>
using namespace std;
 
int R, C, Max;
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
char arr[20][20];
bool visit[26];
 
void dfs(int y, int x, int cnt) {
    
    Max = Max < cnt ? cnt : Max;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + my[i];
        int xx = x + mx[i];
        if (yy >= 0 && yy < R && xx >= 0 && xx < C && !visit[arr[yy][xx]-'A']) {
            visit[arr[yy][xx] - 'A'] = true;
            dfs(yy, xx, cnt + 1);
            visit[arr[yy][xx] - 'A'] = false;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> arr[i][j];
 
    visit[arr[0][0] - 'A'] = true;
    dfs(0, 0, 1);
    cout << Max;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1806번 부분합  (0) 2020.01.31
BOJ 2003번 수들의 합2  (0) 2020.01.31
BOJ 2580번 스도쿠  (0) 2020.01.31
BOJ 2661번 좋은수열  (0) 2020.01.31
BOJ 1759번 암호 만들기  (0) 2020.01.31

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

github : https://github.com/junho0956/Algorithm/blob/master/2580/2580/%EC%86%8C%EC%8A%A4.cpp

 

하나의 실수때문에 2시간이나 날린 문제입니다.. 흑

 

스도쿠를 풀기위한 기본 접근방법은 가로,세로,3*3사각 을 탐색하는것이 아닌

가로,세로,3*3사각 에 맞는 배열을 이용하는 것입니다.

주구장창 탐색만 했다가는 TLE 에 걸립니다.

 

가로, 세로, 9개의 사각형에 대한 사용배열을 미리 만들어두고, dfs 를 통해서 

백트래킹을 하듯이 일단 넣어보고 안되면 리턴하고 이런식으로 코드해주시면 됩니다.

 

가로는 arr 배열의 행 인덱스를 이용해서 row[9][10]; 으로 

세로는 arr 배열의 열 인덱스를 이용해서 col[9][10]; 으로

3*3 사각은 3*3 의 9개 구간을 0,0 0,1 0,2 1,0 1,1 ... 이런식으로 총 3*3 개로 나눈 3차원 visit[3][3][10] 을 사용했습니다

 

실수했던 것은 dfs (int y, int x) 를 받아서 y,x 를 <9 에 해당하는 범위내로 2중포문 돌듯이 구현하였는데

int i = y, ... int j = x 로 하다보니

i 가 다음행으로 증가할때 j 는 0부터 시작해야되는데 x부터 시작하게되는.. 비참한 실수를 하고 말았습니다.

 

이상하게 문제의 예제나 게시판의 반례들은 잘 돌아가길래 결국 처음부터 다시 읽어보니 찾을 수 있었습니다.

좀 더 꼼꼼해야함을 배우고 가는 문제였습니다..

 

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>
 
using namespace std;
 
int arr[9][9];
bool row[9][10];
bool col[9][10];
bool visit[3][3][10];
 
bool check(int i, int j, int k) {
    if (row[i][k]) return false;
    if (col[j][k]) return false;
    if (visit[i / 3][j / 3][k]) return false;
 
    return true;
}
 
bool dfs(int y, int x) {
 
    for (int i = y; i < 9; i++) {
        for (int j = x; j < 9; j++) {
            if (!arr[i][j]) {
                bool temp = false;
                for (int k = 1; k <= 9; k++) {
                    if (check(i, j, k)) {
                        temp = true;
                        arr[i][j] = k;
                        row[i][k] = col[j][k] = visit[i / 3][j / 3][k] = true;
                        if (j < 8) temp = dfs(i, j + 1);
                        else temp = dfs(i + 1, 0);
 
                        if (!temp) {
                            arr[i][j] = 0;
                            row[i][k] = col[j][k] = visit[i / 3][j / 3][k] = false;
                            temp = false;
                        }
                    }
                    if (temp) break;
                }
                if (!temp) return false;
            }
        }
        x = 0;
    }
 
    return true;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    for (int i = 0; i < 9; i++) {
        for (int k = 0; k < 9; k++) {
            cin >> arr[i][k];
            if (arr[i][k]) row[i][arr[i][k]] = true, col[k][arr[i][k]] = true, visit[i / 3][k / 3][arr[i][k]] = true;
        }
    }
 
    bool temp = dfs(0, 0);
 
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2003번 수들의 합2  (0) 2020.01.31
BOJ 1987번 알파벳  (0) 2020.01.31
BOJ 2661번 좋은수열  (0) 2020.01.31
BOJ 1759번 암호 만들기  (0) 2020.01.31
BOJ 5014번 스타트링크  (0) 2020.01.31

+ Recent posts

티스토리툴바