관심이 가는 개발 보물창고

문제 풀이 R, G, B라는 영역이 있을 때, 상하좌우로 인접해있는 영역을 구하는 문제입니다. 중요한 점은 적록색약이 아닌 정상인은 R, G, B 구분할 수 있지만 적록색약인 사람은 R과 G를 같은 색깔로 보게 됩니다. 먼저 정상인 부터 구합니다. 상하좌우로 탐색하면서 R, G, B 를 구분하면서 전체 영역의 개수를 구합니다. 그런 후에 다시 방문 배열을 초기화한 후 적록색약인 사람은 R과 G를 같이 볼 수 있도록 하며, 똑같이 상하좌우로 탐색하면서 영역의 개수를 구하면 됩니다. 탐색 알고리즘은 BFS or DFS 중 하나를 선택해서 구현합니다. 저는 BFS를 이용해서 구현했습니다. 아래의 구현에서 적록색약이 아닌 사람과 적록색약인 사람을 구별하기 위해서 파라미터로 ch1, ch2를 선언했습니다. 정상인..

문제 풀이 각 자리 숫자를 뽑아서 모든 경우의 수를 다 곱해서 정답에 더해주면 됩니다. 문자열로 입력받은 후 각 자리 숫자로 변환한 다음에 계산하면 됩니다. 다만 주의할 점은 정답을 저장할 때 범위를 long long으로 해줘야 합니다. 소스 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string a, b; cin >> a >> b; long long ans = 0; for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b.size(); j++) { int n1 = a[i] - '0'; int n2 = b[j] ..

문제 풀이 문자열이 주어졌을 때 이를 적절하게 섞어서 팰린드롬을 만들 수 있다면, 만들 수 있는 경우에서 사전 순으로 가장 앞서는 문자열을 출력하는 문제입니다. 예제 입력을 잘보면 규칙을 찾을 수 있습니다. 주어진 문자열의 길이가 짝수이면? 팰린드롬을 만들려면 해당 알파벳이 모두 짝수개여야 합니다. 만일 홀수개가 존재한다면 그건 어떤 방법을 사용해도 절대 만들 수 없습니다. 주어진 문자열의 길이가 홀수이면? 팰린드롬을 만들 때 가운데 홀수 알파벳을 제외하고 나머지는 모두 짝수개의 알파벳을 가지고 있어야 만들 수 있습니다. 주의할 점은 홀수 알파벳이 두 개 이상 존재한다면 역시 만들 수 없습니다. A B C D 모두 각각 홀수 1개씩 가지지만 절대 팰린드롬을 만들 수 없는 것처럼 말이죠. 위에서 걸리는 조..

문제 풀이 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다고 합니다. (0,0)이 하얀 칸이면 (0,1)은 검정 칸.. 반복 이랬을 때 규칙을 찾아보면 하얀칸인 좌표는 x + y 가 항상 짝수임을 알 수 있습니다. 따라서 x + y 가 짝수이면서 'F'로 찍힌 곳만 카운팅 해서 출력하면 됩니다. 소스 코드 #include #include using namespace std; char board[8][8]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); for (int i = 0; i > s; for (int j = 0; j < s.size(); j++) { board[i][j] = s[j]; } } int..

문제 풀이 주어진 수가 10보다 작으면, 앞에 0을 붙여서 두 자리로 만들고 각 자리의 숫자 합을 구합니다. 주어진 수의 가장 오른쪽 수와 숫자 합의 가장 오른쪽 수를 붙였을 때 주어진 수가 나올 수 있는 사이클 횟수를 구하는 문제입니다. 주어진 수 : 26 26 => 2 + 6 = 8 (숫자의 합) 68 => 6 + 8 = 14 84 => 8 + 4 = 12 42 => 4 + 2 = 6 26 (4번의 사이클 만에 주어진 수가 나오게 됩니다.) 가장 오른쪽 수를 구할 수 있는 방법은 10을 모듈러 연산하면 쉽게 구할 수 있습니다. 소스 코드 #include #include #include #include #include using namespace std; int main() { ios_base::syn..

문제 풀이 간단한 구현 문제입니다. h가 0일 때만 24로 계산하고, m이 45보다 작을 때만 h를 하나 감소하고 m에다가 60을 더해서 계산하면 됩니다. #include #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int h, m; cin >> h >> m; if (m < 45) { if (h == 0) { h = 23; } else { h--; } m = 60 + m - 45; } else m -= 45; cout

문제 풀이 9^635의 값은 long long 타입도 담을 수 없는 범위의 수이기 때문에, 모듈러를 이용해서 구해야 합니다. 각 숫자마다 제곱수를 만들다 보면, 맨 끝자리의 수가 똑같이 반복되는 구간을 발견할 수 있습니다. 반복되는 구간은 1제곱과 5 제곱이 같고, 2 제곱과 6 제곱이 같고, 3 제곱과 7 제곱이 같고, 4 제곱과 8 제곱이 같습니다. 반복되는 주기를 모듈러를 통해 b의 값을 최적화 시킨 후 답을 구하면 됩니다. 소스 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { int a, b; cin >> a >> b;..

문제 풀이 2차원 배열 형태로 입력이 들어오고, 이것을 인접 리스트 그래프로 만든 후 MST 알고리즘 중 하나인 크루스칼 알고리즘을 적용해서 MST 비용을 구하면 되는 문제입니다. 다만 주의할 점은 i -> j 로 가는 간선과 j -> i 로 가는 간선이 똑같으므로 중복될 수 있기 때문에, 중복을 방지하기 위해서 따로 check 배열로 막았습니다. 또, 간선의 비용이 최대 1억이므로 long long 자료형만 주의해서 구현하면 됩니다. 소스 코드 #include #include #include using namespace std; int N; const int MAX = 1001; int adj[MAX][MAX]; vector edges; int parent[MAX]; bool check[MAX][MAX..

문제 풀이 문제를 요약하면 다음과 같습니다. MST 비용 = MST를 이루고 있는 가중치의 합 각 턴의 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거합니다. 어떤 턴에서는 MST를 만들 수 없다면, 그 턴의 점수는 0점으로 처리합니다. 같은 간선이 여러 번 주어지는 경우는 없습니다. 정리하면 매 턴마다 MST를 구성했을 때, MST를 만들지 못한다면? 0으로 처리하고, MST를 구성했다면 가중치들의 합을 리턴하는 방식으로 문제를 해결해야 합니다. MST를 만들 수 없다는 뜻은 무엇일까요? 문제에서도 나와있듯이 [노드의 개수 != 간선의 개수 + 1] 이여야 합니다. 만약에 위의 조건을 만족했다면 우리는 MST를 만들었다는 뜻이 되기 때문입니다. 따라서 매턴마다 MST를 구..

문제 풀이 숭이는 혜빈이를 위해서 금 빼빼로를 최대한으로 들고 가고 싶어 합니다. 그런데 금 빼빼로를 혜빈이까지 옮기기 위해서는 그만큼의 무게를 견디는 다리가 있어야 하는데요. 어떻게 하면 숭이가 혜빈이까지 움직일 수 있는지 구하는 게 이번 문제입니다. 우선은 최대한 금 빼빼로를 가져다가 주면 좋아하기 때문에, 최대한으로 설정해놓고 움직일 수 있도록 다리를 만들어야 합니다. 기존에 MST를 이용해서 어떻게 하면 최소한의 비용으로 모든 도시들을 연결한 방법이 있었는데, 이것을 반대로 생각해서 최대한의 비용으로 모든 도시들을 연결하게 설정합니다. 왜냐하면 우리는 금 빼빼로를 최대한으로 들고 가야하기 때문입니다. 최대한의 비용으로 그래프를 설계했다면 아래와 같을 것입니다. 노란색으로 색칠한 부분이 우리가 만든..