0과 1의 쉼터

풀이 배추흰지렁이는 인접한 배추(기준이 되는 배추로부터 상하좌우에 위치한 배추)로 퍼져나갈 수 있다. 따라서 인접한 배추들을 전부 탐색하고, visited에 탐색한 배추를 기록하고자 한다. 결국 인접한 배추들의 덩어리인 연결 요소(Connected Component)의 개수를 구하는 문제이다. 배추가 위치한 장소만을 탐색하기 위해 배추의 위치를 입력받을 때 배추의 위치를 location에 기록한 후, DFS의 시행횟수를 세어 풀이했다. 소스코드 소스코드 보기 출처 및 참고자료 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net

풀이 C(N, K)에 대해 N의 범위는 1 ~ 10, K의 범위는 0 ~ N이므로 단순 계산으로 풀이할 수 있다. C(N, K) = N! / (K! * (N - K)! N! = N * (N - 1) * (N - 2) * ... * 1 (N - K) ! = (N - K) * (N - K - 1) * (N - K - 2 ) * ... * 1 이때, N의 sub factorial과 K! 을 구해서 나누어주면 곱셈 횟수를 줄일 수 있다. ex) N = 5, K = 2 5 4 3 2 1 2 1 3 2 1 소스코드 소스코드 보기 출처 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net

풀이 두 좌표를 기준으로 반지름만큼의 원이 형성될 때 원의 둘레가 겹치는 좌표의 개수를 구하면 된다. 아래의 그림은 주어진 Test Case에 대한 시각화 자료이다. 만약 입력으로 주어지는 두 원이, 동일한 좌표와 반지름을 가진다면 '류재명'이 있을 수 있는 위치는 무한대이다. 두 원의 정보에 대한 입력을 struct Circle을 통해 입력받고, 두 원의 중심거리(d)와 두 원의 반지름의 차(diff_radius), 두 원의 반지름의 합(sum_radius)을 구해서 다음과 같은 비교를 통해 문제를 해결할 수 있다. 입력받은 두 원의 정보가 동일하다면 류재명이 있을 수 있는 위치는 무한대이다. d == sum_radius 이거나, d == diff_radius(아래 그림 참고)이면 한 접점에서만 만난다..

풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"와 푸는 방식이 동일한 문제이다. 소스코드 #include int dp[1000001] = {1000001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", back + 1); } 출처 및 참고자료 2..

풀이 i번째 공이 잡을 수 있는 크기는 i번째 공보다 크기가 작고, 색상이 다른 공들의 합이기 때문에, 입력받은 공들을 공의 크기, 색별로 정렬을 해주었다. 출력순서는 입력순서와 동일해야 하므로, 정렬된 정보들에 대해 index별로 담아 줄 수 있는 배열들을 사용했다. for (int i = 0; i < N; i++){ scanf("%d %d", &b[i].color, &b[i].size); b[i].idx = i; } qsort(b, N, sizeof(Ball), compare); int sum_all = 0; for (int i = 0; i < N; i++){ int s = b[i].size, c = b[i].color, idx = b[i].idx; sum_all += s; same_color[c] ..

풀이 index를 이용해 쉽게 풀이할 수 있는 문제다. bubble sort를 했을 때, 정렬이 다 되기까지의 횟수, 즉 요소들이 좌측으로 밀려났 횟수 중 가장 큰 횟수를 찾으면 된다. 입력받을 때 다음과 같이 index를 달아주고, num 10 1 5 2 3 index 0 1 2 3 4 정렬을 하면 다음과 같은 모습이 된다. num 1 2 3 5 10 index 1 3 4 2 0 정렬한 배열의 요소들에 달린 index값에 대해 이전의 index값들을 뺀 값들 중 최댓값이 정답과 일치한다. 소스코드 #include #include #define max(a, b) a > b ? a : b typedef struct{ int num, idx; }Point; int compare(const void *a, c..

풀이 "백준 1149, RGB거리"에 조건이 추가된 문제이다. 입력받은 비용들을 여러 번 사용해야 하고, 처음에 고른 색에 따라 최소비용을 계산해주어야 한다. 소스코드 #include #define MAX 1000001 #define MIN(a,b) (a < b ? a : b) int main(){ int N, result = MAX; scanf("%d", &N); int cost[N][3], min[3] = {0,}, old[3] = {0,}; for (int i = 0; i < N; i++) scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]); for (int i = 0; i < 3; i++){ old[0] = old[1] = old[2] = MAX;..

풀이 부분 수열의 최대 길이를 구한 후 N에서 빼주면 된다. 소스코드 #include int dp[200001] = {200001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", N - (back + 1)); } 출처 및 참고자료 1818번: 책정리 동혁이..

풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"와 동일하지만, 입력받는 숫자들의 범위가 더 크다. 기존 코드로 풀린다. 소스코드 #include int dp[1000001] = {1000001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", ba..

풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"에서 부분 수열의 최대 길이를 lower bound방식으로 빠르게 구했지만, 이렇게 만들어진 임의의 수열들의 요소가 최대 길이를 이루는 요소들이 아님을 예시를 통해 알 수 있었다. 한마디 더 붙이자면, 임시로 생성하는 수열의 최댓값보다 작은 경우에는 lower bound으로 찾은 index위치에 덮어쓰기 때문에 최대 길이를 이루는 요소가 아님을 알 수 있다. 만약 입력받은 요소들이 몇 번째 index에서 덮어쓰기가 되는지 알 수 있다면, 이전의 방법으로 구한 부분 수열의 최대 길이와, 입력받은 요소의 개수 N을 조건에 따라 줄여가면, 요소들을 구할 수 있다. 소스코드 #include #define MAX 1000001 int arr[MAX], te..