0과 1의 쉼터

풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(people)이 또 다른 파티에 참석하게 될 경우 지민이는 마찬가지로 진실만을 말해야 한다. Disjoint Set 구현 풀이 즉, 한 명이라도 진실을 아는 사람이 있는 파티(know_truth)에 참석한 사람들(people)의 Disjoint Set 관계 간 동일 그룹 및 동일 root node를 가지게 되는 것이다. 파티에 참석한 모든 인원을 공통 조상으로 묶어주자. M개의 파티는 진행되는 파티마다 새로 진실을 알게 되는 사람들이(people) 늘어날 수 있으니, 파티를 모두 마친 후 지민이가..

풀이 뱀과 사다리 게임은 쉽게 출발지에서 주사위를 굴려 도착지까지 도달해야 하는 게임이다. 무조건 큰 숫자로 이동하는 '사다리'와 작은 숫자로 이동하는 '뱀' 이지만,'사다리-사다리' 보다 '뱀-사다리'가 더 빠를 수 있다는 점에 유의하자. 즉, 절대적으로 좋고(사다리) 안 좋은(뱀) 조건이 없다. 필자는 개인적으로 뱀을 좋아한다 (~쉬익~쉭) 그 때문에 이동 가능한 모든 칸에 대해서 탐색을 진행해야 한다. 다음 조건을 유의하자 주사위를 굴려 나온 수만큼 이동한 칸에 '사다리' 또는 '뱀'이 있을 때, 선택이 아닌 강제로 이동을 해야한다. '사다리'와 '뱀' 을 동시에 가지는 경우는 없다. 게임은 1회 이상 진행된다. 'N + M

풀이 두 수 A, B가 주어질 때 문제에서 정의된 D, S, L, R 명령을 사용해서 A를 B로 만드는 과정에서 사용한 명령을 순서대로 출력해주면 된다. 시간 제한은 6초로 넉넉한 편이기 때문에 Bidirectional Search 방식을 사용하지 않고, 기본 BFS 방식으로도 해결할 수 있다. 우선, 동일한 숫자가 만들어져 중복된 탐색을 방지하기 위해, 해당 숫자를 만들지 않은 경우에만 만들어줘야한다. queue에 해당 숫자를 만들기 위한 명령어를 set으로 묶어 넣어줘도 되지만, visited 배열에 넣어주기로 했다. 단 위의 방식을 사용할 경우 boolean값이 아닌, 문자열이 탐색 기준이 되기 때문에, 초기값과는 분명히 다른 시작값을 넣어주어야 한다. (초기값 : '-', 시작값 : '') que..

풀이 "백준 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..

풀이 "백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다. 수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌 것 같아 lower bound만을 이용했다. 다음과 같이 수열의 길이만을 계산하기 위해 다음과 같이 수열을 만들었다. i = 0이거나, 생성 중인 수열의 가장 뒷 값보다 큰 경우에는 길이를 늘려준다. 위의 조건이 아닐 때마다, lower bound로 적절한 위치에 입력받은 값을 삽입한다. 10 20 10 11 20 와 같은 수열을 입력 받았다고 가정하자. 앞에서 순차적으로 값이 커지는 경우만 계산을 한다면 10 20으로 최대 길이가 2다. 때문에, 11처럼 20보다는 작지만, 10보다는 큰 경우 ..