문제 : 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

문제 : programmers.co.kr/learn/courses/30/lessons/17677

2018 KAKAO BLINE RECRUITMENT

구현 Simulation

[ 알고리즘풀이 ]

 

 1) 2글자씩 끊어서 둘다 알파벳인지 체크한다.

 2) 두 글자 다 알파벳이라면 소문자로 바꿔준 후, count 배열에 해당 케이스를 저장한다.

     count 배열은 [26][26] 으로 선언해 ['a' ~ 'z']['a' ~ 'z'] 모든 경우를 count 한다.

 3) count 배열을 순회하며 교집합은 count1, count2 배열의 min 값이 되고 합집합은 count1, count2 배열의 max 값이 된다.

 

[ 코드구현 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
include <string>
#include <algorithm>
using namespace std;
 
bool isAlphabet(char c) {
    if ('A' <= c && c <= 'Z') return true;
    if ('a' <= c && c <= 'z') return true;
    return false;
}
 
int solution(string str1, string str2) {
    int cnt1[26][26] = {}, cnt2[26][26] = {};
 
    for (int i = 0; i < str1.length() - 1; i++) {
        if (isAlphabet(str1[i]) && isAlphabet(str1[i + 1])) {
            if ('A' <= str1[i] && str1[i] <= 'Z') str1[i] = (str1[i] - 'A') + 'a';
            if ('A' <= str1[i + 1] && str1[i + 1] <= 'Z') str1[i + 1] = (str1[i + 1] - 'A') + 'a';
            cnt1[str1[i] - 'a'][str1[i + 1] - 'a']++;
        }
    }
 
    for (int i = 0; i < str2.length() - 1; i++) {
        if (isAlphabet(str2[i]) && isAlphabet(str2[i + 1])) {
            if ('A' <= str2[i] && str2[i] <= 'Z') str2[i] = (str2[i] - 'A') + 'a';
            if ('A' <= str2[i + 1] && str2[i + 1] <= 'Z') str2[i + 1] = (str2[i + 1] - 'A') + 'a';
            cnt2[str2[i] - 'a'][str2[i + 1] - 'a']++;
        }
    }
    int andSet = 0, orSet = 0;
    for (int i = 0; i < 26; i++)
        for (int j = 0; j < 26; j++) {
            andSet += min(cnt1[i][j], cnt2[i][j]);
            orSet += max(cnt1[i][j], cnt2[i][j]);
        }
    int answer;
    if (andSet == 0 && orSet == 0) answer = 65536;
    else answer = (andSet * 65536) / orSet;
    return answer;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/Programmers/%5B1%EC%B0%A8%5D_%EB%89%B4%EC%8A%A4_%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81.cpp

 

travelbeeee/ProblemSolving

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

github.com

 

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

[Programmers] 후보키  (0) 2020.09.09
[Programmers] 오픈 채팅방  (0) 2020.04.27
[Programmers] 외벽 점검  (0) 2020.04.27
[Programmers] 기둥과 보 설치  (0) 2020.04.24
[Programmers] 가사 검색 - travelbeeee  (0) 2020.04.23

문제 : programmers.co.kr/learn/courses/30/lessons/4289

2019 KAKAO BLIND RECRUITMENT

bitmask bitmasking

[ 문제해석 ]

 

 속성의 모든 부분 집합 중, 유일성과 최소성을 만족하는 집합을 찾아야한다.

 이때, 유일성은 해당 집합의 속성 값들로 튜플을 구분할 수 있으면 되고, 최소성은 유일성을 만족하는 속성 집합 중에서 하나라도 속성이 빠지면 유일성이 깨지는 경우를 말한다.

 

[ 알고리즘풀이 ]

 

 우리가 다뤄야 될 속성은 최대 8개이므로 bitMask를 이용해서 가능한 모든 속성 조합을 다룰 수 있다.

 예를 들어, 1011(2) = 13 이라는 값은 0번, 1번, 3번 속성을 선택한 경우라고 생각하자.

 그러면, M개의 속성이 있다고 가정하면 (1 ~ 2^M - 1) 값들이 공집합을 제외한 모든 부분 집합을 의미한다.

 

 1) 가능한 모든 속성 집합을 순회하며 유일성을 체크하자.

 

 유일성을 만족한다는 것은 결국 모든 튜플 쌍들에 대해서 현재 속성으로 구분이 가능하다는 뜻이다. 따라서, getBit 함수를 통해 속성들의 index를 얻어내고, 모든 튜플 쌍들에 대해 현재 속성들로 값이 구분되는지 ( 다른 값이 있는지 ) 체크한다.

 

 2) 유일성이 검증된 애들 중 최소성을 체크하자.

 

 최소성은 결국 1번, 2번, 5번 속성으로 유일성을 만족했다면 1번 / 2번 / 5번 / 1번, 2번 / 1번, 5번 / 2번, 5번 으로는 유일성을 만족하지 못해야된다.

 따라서, 유일성을 만족한 애들 중 속성의 갯수를 기준으로 sorting을 한 다음 현재 내가 선택한 속성보다 속성의 갯수가 작은 경우 중 나의 부분 집합이 있는지 체크하면 된다.

 부분집합은 & 연산을 통해서 간단하게 체크가 가능하다.

 예를 들어, 1011과 0011 은 부분집합 관계이므로 1011 & 0011 = 0011 이 성립한다.

 

 

[ 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
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> getBit(int x) {
    vector<int> v;
    int index = 0;
    while (x) {
        if (x % 2) v.push_back(index);
        x /= 2;
        index++;
    }
    return v;
}
 
int getBitCount(int x) {
    int ans = 0;
    while (x) {
        if (x % 2) ans++;
        x /= 2;
    }
    return ans;
}
 
bool compare(int A, int B) {
    return getBitCount(A) <= getBitCount(B);
}
 
int solution(vector<vector<string>> relation) {
    int N = relation.size(), M = relation[0].size();
    int maxSize = (1 << M);
 
    vector<int> bitMask;
    for (int i = 1; i < maxSize; i++) {
        vector<int> cols = getBit(i);
        
        bool isBit = true;
        for (int j = 0; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                bool isDif = false;
                for (int l = 0; l < cols.size(); l++) {
                    if (relation[j][cols[l]] != relation[k][cols[l]]) {
                        isDif = true;
                    }
                }
                if (!isDif) 
                    isBit = false;
            }
        }
        if (isBit) bitMask.push_back(i);
    }
    
   sort(bitMask.begin(), bitMask.end(), compare);
    
    int ans = 0;
    for (int i = 0; i < bitMask.size(); i++) {
        bool isAns = true;
        for (int j = 0; j < i; j++) {
            if ((bitMask[i] & bitMask[j]) == bitMask[j]) isAns = false;
        }
        if (isAns) ans++;
    }
    return ans;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/Programmers/%ED%9B%84%EB%B3%B4%ED%82%A4.cpp

 

travelbeeee/ProblemSolving

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

github.com

 

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

[Programmers] 뉴스 클러스터링  (0) 2020.09.11
[Programmers] 오픈 채팅방  (0) 2020.04.27
[Programmers] 외벽 점검  (0) 2020.04.27
[Programmers] 기둥과 보 설치  (0) 2020.04.24
[Programmers] 가사 검색 - travelbeeee  (0) 2020.04.23

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

DP DynamicProgramming

[ 문제해석 ]

 

 N개의 집에 빨, 초, 파 중 하나의 색깔을 칠할건데 i번 째 집은 (i - 1)번 집, (i + 1)번 집과 색깔이 달라야 한다. 또, 첫 번째 집은 두 번째 집과 마지막 집과 색깔이 달라야된다. (원형)

 이때, 각 집마다 빨, 초, 파 색깔을 칠하는 cost가 주어진다면 모든 집들을 색칠하는데 드는 최소 비용은 얼마일까.

 

[ 알고리즘풀이 ]

 

 1) 점화식

dp[i][0] := (i -1)번 째 집까지 색칠을 다한 상황에서

              i 번 째 집을 0(빨간)색으로 칠할 때 최소 비용 이라고 정의

 

--> i번 째 집을 0(빨간)으로 칠하므로 (i - 1)번 째 집은 1(초록) 혹은 2(파랑) 으로 칠한 상황 중에 더 작은 값을 선택하면 된다.

--> dp[i][0] = color[i][0] + min(dp[i - 1][1], dp[i - 1][2] ) 성립!


다른 dp[i][1], dp[i][2] 도 마찬가지다

 

 2) 원형

우리는 첫 번째 집이 마지막 집에 영향을 끼치는 원형 문제다.
--> 첫 번째 집을 빨 / 초 / 파 3가지 경우로 각각 칠해서 각각 dp 배열을 구해본다.
--> 첫 번째 집을 빨로 칠하면 dp 배열을 채우고, 마지막 집을 초 / 파로 선택한 값들만 사용한다.
--> 마찬가지로 첫 번째 집을 초, 파로 칠하고 점화식을 이용해 dp배열을 채운 후 마지막 집을 다른 색깔로 선택한 값들만 이용한다.

 

[ 코드 구현 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<algorithm>
#include<cstring>
 
using namespace std;
 
const int INF = 99999999;
int N, color[1000][3], ans = INF;
int dp[1000][3];
 
void getCost(void) {
    for (int i = 2; i < N; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + color[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + color[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + color[i][2];
    }
    return;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> color[i][0] >> color[i][1] >> color[i][2];
    
    // 빨간집에서 시작했다고 가정하고 dp배열을 채워보자.
    dp[1][0] = INF, dp[1][1] = color[0][0] + color[1][1], dp[1][2] = color[0][0] + color[1][2];
    getCost();
    ans = min(ans, min(dp[N - 1][1], dp[N - 1][2]));
 
    // 초록집에서 시작했다고 가정하고 dp배열을 채워보자
    memset(dp, 0, sizeof(dp));
    dp[1][0] = color[0][1] + color[1][0], dp[1][1] = INF, dp[1][2] = color[0][1] + color[1][2];
    getCost();
    ans = min(ans, min(dp[N - 1][0], dp[N - 1][2]));
 
    // 파란집에서 시작햇다고 가정하고 dp배열을 채워보자
    memset(dp, 0, sizeof(dp));
    dp[1][0] = color[0][2] + color[1][0], dp[1][1] = color[0][2] + color[1][1], dp[1][2] = INF;
    getCost();
    ans = min(ans, min(dp[N - 1][0], dp[N - 1][1]));
 
    cout << ans << '\n';
 
    return 0;
}
 cs

[ github ]

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

 

travelbeeee/ProblemSolving

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

github.com

 

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

[BOJ] 14226 : 이모티콘  (0) 2020.09.15
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02
[BOJ] 1202 : LOPOV  (0) 2020.08.28
[BOJ] 2636 : 치즈  (0) 2020.08.27

+ Recent posts

티스토리툴바