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




백준에 있는 경사로 문제와 동일하다.


행을 확인할 때는 우측으로 증가하는 경우와, 감소하는 경우를 찾고 불가능한 경우는 걸러낸다.


열을 확인할 때는 하단으로 증가, 감소 경우에 대해서 동일하게 검색한다.



이미 경사로를 건설한 곳에 또 경사로를 건설하지 않도록 해야한다.



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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<iostream>
#include<cmath>
using namespace std;
 
int n, len, map[21][21];
bool used[21][21];
 
bool rowCheck(int i) {
 
    for (int j = 0; j < n-1; j++) {
        if (used[i][j + 1]) continue; //다음 지점에 이미 경사로 있으면
        if (abs(map[i][j] - map[i][j + 1]) >= 2) return false; //2이상 차이
        
        if (map[i][j] == map[i][j + 1] + 1) {
            if (j + len >= n) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = j + 1; k <= j + 1 + len - 2; k++) {
                if (map[i][k] != map[i][k + 1]) return false;
            }
 
            for (int k = j + 1; k <= j + 1 + len - 1; k++) { //이미 경사로가 놓인 경우
                if (used[i][k]) return false;
            }
            
            for (int k = j + 1; k <= j + len; k++) //경사로 표시
                used[i][k] = true;
        }
 
    }
 
    for (int j = 0; j < n-1; j++) {
        if (used[i][j + 1]) continue; //다음 지점에 이미 경사로 있으면
        
        if (map[i][j] == map[i][j + 1] - 1) {
            if (j + 1 - len < 0) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = j + 1 - len; k <= j - 1 ; k++) {
                if (map[i][k] != map[i][k + 1]) return false;
            }
 
            for (int k = j + 1 - len; k <= j; k++) { //이미 경사로가 놓인 경우
                if (used[i][k]) return false;
            }
 
            for (int k = j + 1 - len; k <= j ; k++) //경사로 표시
                used[i][k] = true;
        }
    }
    return true;
}
 
bool colCheck(int j) {
    for (int i = 0; i < n - 1; i++) {
        if (used[i+1][j]) continue; //다음 지점에 이미 경사로 있으면
        if (abs(map[i][j] - map[i+1][j]) >= 2) return false; //2이상 차이
 
        if (map[i][j] == map[i+1][j] + 1) {
            if (i + len >= n) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = i + 1; k <= i + 1 + len - 2; k++) {
                if (map[k][j] != map[k+1][j]) return false;
            }
 
            for (int k = i + 1; k <= i + 1 + len - 1; k++) {
                if (used[k][j]) return false;
            }
 
            for (int k = i + 1; k <= i + len; k++) //경사로 표시
                used[k][j] = true;
        }
 
    }
 
    for (int i = 0; i < n - 1; i++) {
        if (used[i+1][j]) continue; //다음 지점에 이미 경사로 있으면
 
        if (map[i][j] == map[i+1][j] - 1) {
            if (i + 1 - len < 0) return false; //경사로 지으면 밖으로 나가는 경우
 
            for (int k = i + 1 - len; k <= i - 1; k++) {
                if (map[k][j] != map[k+1][j]) return false;
            }
 
            for (int k = i + 1 - len; k <= i; k++) {
                if (used[k][j]) return false;
            }
 
            for (int k = i + 1 - len; k <= i; k++) //경사로 표시
                used[k][j] = true;
        }
    }
 
    return true;
}
 
int process() {
    int ret = 0; //활주로로 사용가능한 길
 
    for (int i = 0; i < n; i++) {
        if (!rowCheck(i)) //가로방향 확인
            continue;
        ret++;
    }
 
    //경사로 초기화
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            used[i][j] = false;
 
 
    for (int j = 0; j < n; j++) {
        if (!colCheck(j)) 
            continue;
        ret++;
    }
    
    return ret;
}
 
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
    
    for (int t = 1; t <= T; t++) {
        cin >> n >> len;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
 
        int res = process();
 
        cout << "#" << t << ' ' << res << '\n';
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = 0;
 
        //경사로 초기화
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                used[i][j] = false;
 
    }
 
    return 0;
}
 
cs


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

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

SWEA 2382: 미생물 격리 (C++)  (0) 2019.10.16
SWEA 2383: 점심 식사시간 (C++)  (0) 2019.10.15
SWEA 2105: 디저트 카페 (C++)  (0) 2019.10.15
SWEA 5656: 벽돌 깨기 (C++)  (0) 2019.10.14
SWEA 2115: 벌꿀채취 (C++)  (0) 2019.10.14

모든 경우에 대해서 완전 탐색을 해주면 된다.


결정하는 달에 이용 내역이 없으면 비용 추가 없이(이용권 구매 없이) 다음 달로 넘어간다.



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
#include<iostream>
#define INF 987654321;
using namespace std;
 
int price[4], plan[15], Min = INF;
 
void dfs(int month, int fee) {
    if (month >= 12) {
        if (fee < Min) Min = fee;
        
        return;
    }
    
    //(month + 1)월 어떻게 낼건지 결정
 
    if (plan[month + 1] == 0) //그 달에 이용 내역이 없으면 비용 추가 없이 월 추가
        dfs(month + 1, fee);
    
    else {
        dfs(month + 1, fee + price[0] * plan[month + 1]); //1일
        dfs(month + 1, fee + price[1]); //1달
        dfs(month + 3, fee + price[2]); //3달
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        for (int i = 0; i < 4; i++)
            cin >> price[i]; // 1일, 1달, 3달 1년
        
        
        for (int i = 1; i <= 12; i++)
            cin >> plan[i];
        
        if (Min > price[3]) Min = price[3]; // 1년치
        
        dfs(0, 0);
        cout << "#" << tc << ' ' <<  Min << '\n';
        Min = INF; //Min 초기화
    }
    return 0;
}
 
 
cs


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

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

SWEA 5644: 무선 충전 (C++)  (0) 2019.10.09
SWEA 4008번: 숫자 만들기 (C++)  (0) 2019.10.08
SWEA 4013번: 특이한 자석 (C++)  (0) 2019.10.03
SWEA 4012번: 요리사 (C++)  (0) 2019.10.03
SWEA 1244번: 최대 상금 (C++)  (2) 2019.09.27

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://programmers.co.kr/learn/courses/30/lessons/42840

 

알고리즘 연습 - 모의고사 | 프로그래머스

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3,

programmers.co.kr

 

수포자가 수학을 찍는 규칙을 확인해서, 등수를 가려내는 문제이다.

 

코드를 좀 더 깔끔하게 구현할 수 있을텐데 직관적으로 빠르게 구현하고자 했기 때문에 코드가 다소 난잡하다.

 

먼저 세 학생의 답안 마킹 방법을 배열로 설정해뒀다.

 

이어서 맞은 개수와, 학생 index pair를 벡터에 넣고 정렬을 수행했다.

 

정렬 조건을 만들어주는 bool 함수만 조심해서 구현하고, 문제 조건에 맞게 조건문을 작성해준다.

 

#include <string>
#include <vector>
#include<bits/stdc++.h>

using namespace std;
int fir[10000];
int sec[10000];
int thr[10000];
bool cmp(pair<int, int> a, pair<int, int> b){
    //T 면 a가 앞
    if(a.second > b.second)
        return true;
    else 
        return false;
}
vector<int> solution(vector<int> answers) {
    vector<int> answer;
    for(int i = 0 ; i < 10000 ; i ++){
        if(i % 5 == 0) fir[i] = 1;
        else if(i % 5 == 1) fir[i] = 2;
        else if(i % 5 == 2) fir[i] = 3;
        else if(i % 5 == 3) fir[i] = 4;
        else if(i % 5 == 4) fir[i] = 5;
    }
    for(int i = 0 ; i < 10000 ; i ++){
        if(i % 2 == 0) sec[i] = 2;
        else if(i % 8 == 1) sec[i] = 1;
        else if(i % 8 == 3) sec[i] = 3;
        else if(i % 8 == 5) sec[i] = 4;
        else if(i % 8 == 7) sec[i] = 5;
    }
    for(int i = 0 ; i < 10000 ; i++){
        if(i % 10 == 0 || i % 10 == 1) thr[i] = 3;
        else if(i % 10 == 2 || i % 10 == 3) thr[i] = 1;
        else if(i % 10 == 4 || i % 10 == 5) thr[i] = 2;
        else if(i % 10 == 6 || i % 10 == 7) thr[i] =4;
        else if(i % 10 == 8 || i % 10 == 9) thr[i] =5;
    }
    vector<pair<int, int> > v{ {1,0}, {2,0}, {3,0} } ;
    for(int i = 0 ; i < answers.size() ; i++){
        if(fir[i] == answers[i]) v[0].second++;
        if(sec[i] == answers[i]) v[1].second++;
        if(thr[i] == answers[i]) v[2].second++;
    }
    sort(v.begin(), v.end(), cmp);
    
    if(v[0].second != 0){
       if(v[0].second != v[1].second)
           answer.push_back(v[0].first);
        else{
            if(v[1].second == v[2].second){
                answer.push_back(v[0].first);
                answer.push_back(v[1].first);
                answer.push_back(v[2].first);
                }
            else{
                answer.push_back(v[0].first);
                answer.push_back(v[1].first);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}
저작자표시 비영리 변경금지

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

카카오 2018 블라인드 테스트: 실패율 C++  (0) 2019.08.19
카카오 2018 블라인드 테스트: 오픈채팅방 C++  (0) 2019.08.19
프로그래머스: 완주하지 못한 선수 (C++)  (0) 2019.07.09
프로그래머스: 가장 큰 수 (C++)  (0) 2019.07.09
프로그래머스: K번째수 (C++)  (0) 2019.07.05

+ Recent posts

티스토리툴바