문제 : www.acmicpc.net/problem/1747

에라토스테네스체

[ 알고리즘풀이 ]

 

 N에서 시작해 소수이면서 팰린드롬인 숫자를 찾을 때까지 N보다 크거나 같은 수를 순회한다. 

 1) 소수인지 체크

 : 에라토스테네스 체를 이용해 입력 최댓값인 100만 보다 넉넉히 큰 1000만까지 소수를 다 구해놓는다.

 --> 입력 최대값인 100만을 입력했을 때 정답이 100,3001 이므로 1000만까지 안 해도 됐었다...!!

 

 2) 팰린드롬인지 체크

 : 숫자의 각 자리를 추출해서 vector에 담아두고 팰린드롬인지 체크하면 된다.

 

[ 코드구현 C++ ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
bool isPrime[10000001];
 
void eratos() {
    isPrime[0] = isPrime[1] = true;
    for (int i = 2; i <= 10000000; i++) {
        if (!isPrime[i]) {
            for (int j = 2 * i; j <= 10000000; j += i)
                isPrime[j] = true;
        }
    }
}
 
bool isPalindrome(int x) {
    vector<int> numbers;
    while (x) {
        numbers.push_back(x % 10);
        x /= 10;
    }
    bool ans = true;
    for (int i = 0; i < ((int)numbers.size() / 2); i++) {
        if (numbers[i] != numbers[numbers.size() - 1 - i]) ans = false;
    }
    return ans;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    eratos();
    int N, x;
    cin >> N;
 
    x = N;
    while (1) {
        if (!isPrime[x] && isPalindrome(x)){
            cout << x << '\n';
            break;
        }
        x++;
    }
    return 0;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1747.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 9202 : Boggle  (0) 2020.09.17
[BOJ] 14226 : 이모티콘  (0) 2020.09.15
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02

문제 : www.acmicpc.net/problem/9202

Sort Backtracking BinarySearch

[ 알고리즘풀이 ]

 

-Sorting

1) 단어사전을 입력받고 sort를 진행한다. ( binary search 를 위해 )

 

-Backtracking

2) 4 x 4 보드 판을 입력받고, 모든 지점에서 만들 수 있는 모든 단어를 Backtracking 을 이용해서 만든다.

 

-BinarySearch 

3) 만들어진 단어가 단어사전에 있는지 binary search를 이용해 탐색한다.

 

4) 이진탐색 결과가 실패라면 넘어가고, 성공이라면 가장 긴 단어와 score, 단어 count를 갱신한다.

이때, 같은 단어를 만들어서 찾은 경우라면 한 번만 count 해야 되므로 isSelected bool 배열을 이용해 단어 사전에서 탐색에 성공한 단어들은 체크해둔다.

 

 5) (2) ~ (4) 과정을 보드판마다 반복한다.

 

[ 코드구현 C++ ]

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
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
int w, b;
int scores[9] = { 0, 0, 0, 1, 1, 2, 3, 5, 11 };
int dx[8] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
 
string dictionary[300000];
 
int cnt, score;
bool isSelected[300000];
bool visited[4][4];
string board[4];
string longWord;
 
bool isInside(int x, int y) {
    return (0 <= x && x < 4 && 0 <= y && y < 4);
}
 
int binary_search(string word) {
    int left = 0, right = w - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (dictionary[mid] == word) return mid;
        else if (dictionary[mid] < word) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
 
void makeWord(int x, int y, string word) {
    if (int(word.length()) >= 9) return;
    if (word.length() >= 1) {
        // binarySearch로 찾기
        int ind = binary_search(word);
        if (ind != -1) {
            if (word.length() > longWord.length()) longWord = word;
            else if (word.length() == longWord.length() && word < longWord) longWord = word;
            if (!isSelected[ind]) {
                isSelected[ind] = 1;
                cnt++;
                score += scores[word.length()];
            }
        }
    }
 
    for (int i = 0; i < 8; i++) {
        int nextX = x + dx[i], nextY = y + dy[i];
        if (!isInside(nextX, nextY)) continue;
        if (visited[nextX][nextY]) continue;
 
        visited[nextX][nextY] = 1;
        word.push_back(board[nextX][nextY]);
        makeWord(nextX, nextY, word);
        word.pop_back();
        visited[nextX][nextY] = 0;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> w;
    for (int i = 0; i < w; i++)
        cin >> dictionary[i];
 
    sort(dictionary, dictionary + w);
 
    cin >> b;
    for (int i = 0; i < b; i++) {
        for (int j = 0; j < 4; j++)
            cin >> board[j];
 
        memset(isSelected, 0, sizeof(isSelected));
        longWord = "";
        cnt = 0;
        score = 0;
 
        string word;
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++){
                word.push_back(board[j][k]);
                visited[j][k] = 1;
                makeWord(j, k, word);
                visited[j][k] = 0;
                word.pop_back();
            }
        cout << score << ' ' << longWord << ' ' << cnt << '\n';
    }
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9202.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1747 : 소수 & 팰린드롬  (0) 2020.09.18
[BOJ] 14226 : 이모티콘  (0) 2020.09.15
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02

문제 : www.acmicpc.net/problem/14226

BFS

[ 알고리즘풀이 ]

 

 BFS 탐색을 이용해 현재 화면에 있는 이모티콘의 개수와 클립보드에 있는 이모티콘의 개수 정보를 갱신해나가며 답을 구할 수 있다.

 우리는 현재 상태에서 다음 3가지 행동을 할 수 있다.

1) 현재 화면의 이모티콘 개수와 클립보드에 있는 개수가 다르다면 클립보드에 새롭게 복사한다.

2) 현재 클립보드에 있는 개수가 0이 아니라면 현재 화면에 붙여넣기를 한다.

3) 현재 화면에 이모티콘이 0개가 아니라면 하나를 삭제한다.

 

 이렇게 3가지 동작을 수행할 수 있고, 구해야하는 이모티콘의 개수가 S개라면 클립보드에 S 보다 큰 값을 저장하는 경우는 항상 최소가 아니게 되고, 화면에 있는 이모티콘의 개수가 2 * S 가 넘어가는 경우도 최소가 아니게 된다. 따라서, 우리는 화면에 있는 이모티콘의 개수( 0  ~  2 * S ), 클립보드에 있는 이모티콘의 개수 ( 0 ~  S) 가 성립하는 경우만 다루면 된다.

 

[ 코드구현 C++ ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
const int INF = 99999999;
int S;
int visited[2001][1001] = {};
 
bool isInside(int x, int y) {
    return (0 <= x && x <= 2 * S && 0 <= y && y <= S);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> S;
 
    for (int i = 0; i <= 2 * S; i++)
        for (int j = 0; j <= S; j++)
            visited[i][j] = INF;
 
    queue<pair<int, int>> q;
 
    q.push({ 1, 0 });
    visited[1][0] = 0;
    while (!q.empty()) {
        int curE = q.front().first, curC = q.front().second;
        q.pop();
        if (curE == S) {
            cout << visited[curE][curC] << '\n';
            break;
        }
 
        // 복사
        if (curC != curE) {
            if (isInside(curE, curE) && visited[curE][curC] + 1 < visited[curE][curE]) {
                visited[curE][curE] = visited[curE][curC] + 1;
                q.push({ curE, curE });
            }
        }
        // 붙여넣기
        if (curC != 0 && isInside(curE+curC, curC) && visited[curE][curC] + 1 < visited[curE + curC][curC]) {
            visited[curE + curC][curC] = visited[curE][curC] + 1;
            q.push({ curE + curC, curC });
        }
        // 이모티콘 삭제
        if (isInside(curE - 1, curC) && visited[curE][curC] + 1 < visited[curE - 1][curC]) {
            visited[curE - 1][curC] = visited[curE][curC] + 1;
            q.push({ curE - 1, curC });
        }
    }
 
    return 0;
}}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ14226.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1747 : 소수 & 팰린드롬  (0) 2020.09.18
[BOJ] 9202 : Boggle  (0) 2020.09.17
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02

문제 : www.acmicpc.net/problem/1107

백트레킹 브루트포스

[ 알고리즘풀이 ]

 우리는 최대 N이 500,000 이므로 고장나지 않은 버튼들로 0 ~999,999 까지만 만들어보면 된다.

 고장나지 않은 버튼들로 한 번 숫자를 다 만들고 나서부터는 +, - 버튼 말고 누르는 의미가 없으므로,

 0 ~ 999,999 까지 고장나지 않은 버튼들로 만들 수 있는 숫자를 다 만들어 최소 버튼 누르는 횟수를 저장하고 N까지 이동하는데 눌러야되는 +, - 버튼의 횟수를 계산해 최소값을 찾으면 된다.

 

[ 코드구현 C++ ]

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
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
 
using namespace std;
 
int N, visited[1000001] = {}, K;
bool isBroken[10] = {};
queue<int> q;
 
void makeChannel(string s) {
    for (int i = 0; i < 10; i++) {
        if (!isBroken[i]) {
            s += ('0' + i);
            if (stoi(s) <= 1000000) {
                //cout << "만들어진 채널 : " << s << endl;
                visited[stoi(s)] = s.length();
                makeChannel(s);
            }
            s.pop_back();
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    memset(visited, -1, sizeof(visited));
    cin >> N >> K;
    for (int i = 0, x; i < K; i++) {
        cin >> x;
        isBroken[x] = 1;
    }
    // 만들 수 있는 모든 수 들을 만들어본다.
    if (!isBroken[0]) visited[0] = 1;
    for (int i = 1; i < 10; i++) {
        if (!isBroken[i]) {
            string t = "";
            t.push_back('0' + i);
            visited[i] = 1;
            makeChannel(t);
        }
    }
    visited[100] = 0;
 
    int ans = 999999999;
    for (int i = 0; i <= 1000000; i++) {
        if (visited[i] != -1) {
            ans = min(ans, abs(N - i) + visited[i]);
        }
    }
    cout << ans << '\n';
    return 0;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1107.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 9202 : Boggle  (0) 2020.09.17
[BOJ] 14226 : 이모티콘  (0) 2020.09.15
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02
[BOJ] 1202 : LOPOV  (0) 2020.08.28

+ Recent posts

티스토리툴바