https://www.welcomekakao.com/learn/courses/30/lessons/42842


모든 격자 수의 합이 갈색과 빨간색의 합이 된다.


곱해서 합이 되는 경우를 구하면 카펫의 가로와 세로를 구할 수 있고, 구한 값에 대해서 가운데에


빨간색 격자의 수를 감당할 수 있는지 확인해준다.



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
#pragma warning(disable :4996)
#include<iostream>
#include<vector>
using namespace std;
 
int Sum;
vector<int> solution(int br, int red) {
    vector<int> ans;
 
    Sum = br + red; //전체 격자의 수
    int h; //높이
    for (int w = Sum; w >= 1; w--) {
 
        if (Sum % w == 0) {
            h = Sum / w;
            if (w < h) break; //가로가 세로보다 길거나 같을때만 보면됨
            if ((w - 2)*(h - 2) == red) {
                ans.push_back(w);
                ans.push_back(h);
            }
        }
    }
    return ans;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 단어 변환 (C++)  (0) 2019.09.29
프로그래머스: 네트워크 (C++)  (0) 2019.09.28
프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27
프로그래머스: 소수찾기 (C++)  (0) 2019.09.27
프로그래머스: 타겟 넘버 (C++)  (0) 2019.09.20

https://www.welcomekakao.com/learn/courses/30/lessons/42841


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
#include <string>
#include <vector>
#include<iostream>
#include<set>
using namespace std;
 
bool used[10];
int arr[3];
vector<vector<int> > v; 
int ans = 0;
 
void btk(int k, vector<vector<int> > &clue) {
    if (k == 3) {
        // 후보로 만들어낸 수
        int candi = arr[0] * 100 + arr[1] * 10 + arr[2];
 
        string candiStr = to_string(candi);
        for (int i = 0; i < clue.size(); i++) {
            int stkCnt = 0, ballCnt = 0;
 
            for (int j = 0; j < candiStr.length(); j++) {
                //char를 int로 바꿔서 비교
                if (candiStr[j] - '0' == v[i][j]) //스트라이크 조건
                    stkCnt++;
                else {
                    for (int m = 0; m < 3; m++) { //볼 조건
                        if (candiStr[j] - '0' == v[i][m])
                            ballCnt++;
                    }
                }
            }
 
            if (stkCnt != clue[i][1] || ballCnt != clue[i][2]) return;
        }
        ans++;
        return;
    }
 
    for (int i = 1; i <= 9; i++) {
        if (!used[i]) {
            arr[k] = i;
            used[i] = true;
            btk(k + 1, clue);
            used[i] = false;
        }
    }
}
 
int solution(vector<vector<int>> clue) {
    vector<int> numlist;
    for (int i = 0; i < clue.size(); i++) {
        int tmp = clue[i][0];
        string strtmp = to_string(tmp);
        //힌트로 들어오는 숫자를 자릿수별로 끊어서 벡터에 저장
        numlist.push_back(stoi(strtmp.substr(0, 1)));
        numlist.push_back(stoi(strtmp.substr(1, 1)));
        numlist.push_back(stoi(strtmp.substr(2, 1)));
        v.push_back(numlist);
        numlist.clear();
    }
 
    btk(0, clue);
    return ans;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 네트워크 (C++)  (0) 2019.09.28
프로그래머스: 카펫 (C++)  (0) 2019.09.28
프로그래머스: 소수찾기 (C++)  (0) 2019.09.27
프로그래머스: 타겟 넘버 (C++)  (0) 2019.09.20
프로그래머스: 문자열 내 p와 y의 개수 (C++)  (0) 2019.09.20

주어지는 수의 모든 자리에 대해서 숫자를 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include<iostream>
#include<string>
 
using namespace std;
 
string org, tmp;
int n; //n번 스왑
int Max;
void dfs(int here, int cnt) { //인덱스 here과 바꿀곳 검색
    if (cnt == n) {
        int candi = stoi(org);
        if (Max < candi) Max = candi;
 
        return;
    }
    
    for (int i = here; i < org.length(); i++) {
        for (int j = i + 1; j < org.length(); j++) {
            if (org[i] <= org[j]) { //수가 작아지지 않도록
                int temp = org[i];
                org[i] = org[j];
                org[j] = temp;
                
                dfs(i, cnt + 1);
 
                temp = org[i];
                org[i] = org[j];
                org[j] = temp;
            }
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> org >> n;
        Max = stoi(org);
        dfs(0, 0);
        cout << '#'<<tc<< ' ' << Max << '\n';
    }
    return 0;
}
 
 
cs



저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 3752번: 가능한 시험 점수 (C++)  (0) 2019.09.27
SWEA 2814: 최장 경로 (C++)  (0) 2019.09.25

https://www.welcomekakao.com/learn/courses/30/lessons/42839


주어지는 문자열에서, 1개~ 문자열길이만큼 숫자를 뽑아서 수를 만들어보고, 소수라면 set에 담는다.


숫자의 중복을 방지하기 위해서 set을 사용했다.


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
#include <string>
#include <vector>
#include<iostream>
#include<set>
using namespace std;
 
set<int> candi; //중복 방지를 위해 set 이용
vector<char> v;
bool used[10];
int Sz, arr[8];
 
bool isPrime(int k) {
    if (k == 0 || k == 1) return false;
    
    for (int i = 2; i*i <= k; i++) {
        if (k % i == 0) return false;
    }
    return true;
}
void btk(int k, int cnt, string &nums) {
    if (k == cnt) {
        
        string tmp = "";
        for (int i = 0; i < k; i++) 
            tmp += nums[arr[i]];
        
        int intTmp = stoi(tmp);
        
        if(isPrime(intTmp)) //만든 숫자가 소수인 경우에만 set에 추가
            candi.insert(intTmp);
    
        return;
    }
    
    for (int i = 0; i < Sz; i++) {
        if (!used[i]) {
            arr[k] = i; //nums의 인덱스를 넣음
            used[i] = true;
            btk(k + 1, cnt, nums);
            used[i] = false;
        }
    }
}
 
int solution(string nums) {
    Sz = nums.length();
    for (int i = 1; i <= nums.length(); i++) 
        btk(0, i, nums);
    
    return (int)candi.size();
}
 
int main(void) {
    solution("011");
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 카펫 (C++)  (0) 2019.09.28
프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27
프로그래머스: 타겟 넘버 (C++)  (0) 2019.09.20
프로그래머스: 문자열 내 p와 y의 개수 (C++)  (0) 2019.09.20
프로그래머스: 전화번호 목록  (0) 2019.09.19

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE



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
27
28
29
30
31
32
33
34
35
36
37
38
#pragma warning(disable :4996)
#include<iostream>
#include<vector>
using namespace std;
bool vis[10001]; //최대 만점
int n;
vector<int> v;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        
        v.push_back(0);
        vis[0] = true;
        int val;
        for (int i = 0; i < n; i++) {
            cin >> val;
            int curSize = v.size(); //새로운 숫자 넣기 직전에 백터 크기
            for (int j = 0; j < curSize; j++) {
                int candi = val + v[j]; //추가될 수 있는 수
                if (!vis[candi]) { //이미 추가된 수면 pass
                    v.push_back(candi);
                    vis[candi] = true;
                }
            }
        }
        cout  << '#' << tc << ' ' << v.size() << '\n';
        v.clear();
        for (int i = 0; i <= 10000; i++)
            vis[i] = false;
    }
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글

SWEA 1952: 수영장 (C++)  (0) 2019.10.04
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27
SWEA 2814: 최장 경로 (C++)  (0) 2019.09.25

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


최단거리를 구해야하고, 간선이 음이 아니면서 모두 같은 상황이 아니기 때문에 다익스트라를 이용해야 한다.



0. 시작점에서 특정 지점까지 가는 비용(거리, 시간...) 무한대로 초기화

0. pair 자료구조의 sorting을 활용하기 위해서 {dist[], 지점} 으로 사용.

1. 시작점 pq에 push(min heap)


2. pq에서 하나 꺼내고, pop하고 꺼낸 지점 방문처리


3. 이동할 수 있는 지점 확인. 범위 밖이거나, 이미 방문한 지점이면 pass


4. 시작점에서 이동할 수 있는 지점까지의 거리 > 시작점에서 현재 지점까지 거리 + 현재 지점에서 이동할 수 있는 지점까지 가는 비용

이라면 좌변을 우변으로 갱신. pq에 push


5. 목적지를 방문처리하고, 이동이 완료되면 종료



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
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
#include<functional>
#include<limits.h> //이 헤더로 해야 백준에서 돌아감
 
using namespace std;
typedef pair<int, int> pii;
 
int dis[100001], src, dst;
bool vis[100001];
priority_queue<pii, vector<pii>, greater<pii> > pq;
 
void dijk() {
    pq.push({ 0, src }); //{그 지점까지 가는 비용, 지점}
    dis[src] = 0;
 
    while (!pq.empty()) {
        int here = pq.top().second; //현재 확인하는 지점
        pq.pop();
        vis[here] = true; //방문처리
        
        int there, moveCost; //다음 방문지점, here에서 there로 가는 비용
 
        for (int i = 0; i < 3; i++) {
            //0앞으로 걷기, 1뒤로걷기, 2점프
            if (i == 0)
                there = here + 1;
            else if (i == 1) there = here - 1;
            else
                there = here * 2;
 
            if (i != 2)
                moveCost = 1;
            else
                moveCost = 0;
 
            if (there < 0 || there > 100000 || vis[there]) continue;
 
            //이미 계산된 src에서 there까지 가는 비용이
            //src~here 비용 + here~there비용보다 크면 갱신하고 pq에 삽입
            if (dis[there] > dis[here] + moveCost) { 
                dis[there] = dis[here] + moveCost;
                pq.push({ dis[there], there });
            }
        }
        if (here == dst) return; //목적지가 방문처리 되었으므로 확인 그만
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    for (int i = 0; i <= 100000; i++)
        dis[i] = INT_MAX; //무한대로 초기화
 
    cin >> src >> dst;
 
    dijk();
 
    cout << dis[dst];
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 17472번: 다리만들기2 (C++)  (0) 2019.10.19
백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26

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



다음번에 물이 확산할 곳으로는 이동할 수 없다고 했으므로, 물의 확산을 먼저 수행해준다.


그리고 길이 1만큼 이동 가능한 경우를(특정 시점에 들어있는 큐의 크기만큼만) BFS를 수행해서


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
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
101
102
103
104
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
 
using namespace std;
typedef pair<int, int> pii;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
 
int R, C;
char m[51][51];
int dis[51][51];
 
pii st;
queue<pii> q;
queue<pii> fldq;
bool fldVis[51][51];
 
void fldbfs() {
    int qs = fldq.size();
    while (qs--) { //한 번의 확산만 일어나도록
        pii cur = fldq.front();
        fldq.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if (fldVis[nr][nc] || m[nr][nc] =='D' || m[nr][nc] == 'X') continue;
            m[nr][nc] = '*';
        }
    }
}
 
void flood() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (!fldVis[i][j] && m[i][j] == '*') {
                fldq.push({ i, j }); //확산 지점들 미리 push
                fldVis[i][j] = true;
            }
        }
    }
    fldbfs();
}
void bfs() {
    q.push(st);
    dis[st.first][st.second]++;
 
    while (!q.empty()) {
        int qs = q.size();
        //물이동 먼저 하고, 길이 1만큼 이동하도록
 
        flood();
        while (qs--) {
            
            pii cur = q.front();
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int nr = cur.first + dr[i];
                int nc = cur.second + dc[i];
                if (nr < 0 || nc < 0 || nr >= R || nc >= C || dis[nr][nc] >= 0)
                    continue;
                
                if (m[nr][nc] == '*' || m[nr][nc] == 'X') continue;
                
                q.push({ nr, nc });
                dis[nr][nc] = dis[cur.first][cur.second] + 1;
                
                if (m[nr][nc] == 'D') {
                    cout << dis[nr][nc];
                    return;
                }
            }
        }
    }
    
    cout << "KAKTUS";
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    //*물, X돌, 비버굴D, 고슴도치S
    
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            dis[i][j] = -1;
            if (m[i][j] == 'S') {
                st.first = i;
                st.second = j;
            }
        }
    }
 
    bfs();
    
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26

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



주어진 문자열을 처음부터 끝까지 한 번만 검사한다.


검사하면서, 폭발 단어의 마지막 철자와 같은 철자가 나오면, 현재까지 만들어둔 정답이 폭발 단어를 포함하는지 확인한다.


만약 포함한다면, 필요한 횟수만큼 pop_back 해주고, 그렇지 않으면 이어서 해당 철자를 이어서 붙여준다.



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
#include<iostream>
#include<string>
 
using namespace std;
 
string ans = "";
int main(void) {
    string str, bomb;
    cin >> str >> bomb;
    
    int k = 0; //str의 길이만큼 확인 (확인할 인덱스)
    while (k < (int)str.length()) {
 
        //단어폭탄의 마지막 문자와 같으면서, 단어 폭탄의 길이 이상의 단어가 ans 문자열에 들어 있을 때만 검사
        if (str[k] == bomb[bomb.length() - 1] && ans.length() >= bomb.length()-1) {
            bool isBomb = true;
            int idx = 0;
            for (int j = 1; j <= bomb.length()-1; j++) { //마지막 문자는 어짜피 같으니까, 제외하고 검사
                if (ans[ans.length() - bomb.length() + j] != bomb[idx]) {
                    isBomb = false;
                    break;
                }
                else
                    idx++;
            }
            if (isBomb) { //단어 폭탄인 경우 
                for (int i = 0; i < bomb.length() - 1; i++)
                    ans.pop_back();
            }
            else //폭탄검사를 했는데 아닌 경우
                ans += str[k];
        }
        else { //단어 폭탄의 마지막 철자와 글자가 달랐던 (평범한) 경우
            ans += str[k];
        }
        k++; //확인하는 문자열 위치 증가
    }
    if ((int)ans.length() != 0)
        cout << ans;
    else
        cout << "FRULA"; 
    return 0;
}
cs




저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26
백준 2941번: 크로아티아 알파벳 (C++)  (0) 2019.09.26

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


set에 들어보지 못한 사람 저장하고, 처음 본사람 이름을 받으면서 set에 있으면 결과 벡터에 담고, 마지막에 정렬 이후 출력


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
#pragma warning(disable :4996)
#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
set<string> lis;
vector<string> see;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        lis.insert(temp);
    }
    
    for (int i = 0; i < m; i++) {
        string temp;
        cin >> temp;
        if (lis.find(temp) != lis.end()) //lis set에 존재하면 결과에 push
            see.push_back(temp);
    }
    
    sort(see.begin(), see.end());
    cout << see.size() << '\n';
    for (int i = 0; i < see.size(); i++)
        cout << see[i] << '\n';
    
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26
백준 2941번: 크로아티아 알파벳 (C++)  (0) 2019.09.26
백준 1316번: 그룹 단어 체커 (C++)  (0) 2019.09.25

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




문자열을 입력 받을 때마다, 달라지는 부분을 '?'로 변경해주면 된다.



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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<string> v;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //첫 입력으로 초기화 하고, 다른 부분 ?로 다 바꾸기(이미 ?가 아닌 경우에)
    int n;
    cin >> n;
    string str;
    cin >> str;
    for (int i = 0; i < n - 1; i++) {
        string val;
        cin >> val;
        
        for (int i = 0; i < str.length(); i++) {
            if (str[i] != '?' && str[i] != val[i])
                str[i] = '?';
        }
 
    }
    cout << str;
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 2941번: 크로아티아 알파벳 (C++)  (0) 2019.09.26
백준 1316번: 그룹 단어 체커 (C++)  (0) 2019.09.25
백준 1157번: 단어 공부 (C++)  (0) 2019.09.25

+ Recent posts

티스토리툴바