0과 1의 쉼터

풀이 "백준 11726, 2×n 타일링" 문제와 비슷하다. 심지어 정답도.. 2x1 타일을 1, 1x2 타일을 2, 2x2 타일을 T라고 가정할 때 다음과 같이 나타낼 수 있다. N 타일 dp[1] 2 11 2, T 3 3 111 12,1T 21,2T 5 4 1111 112,11T 121,1T1 211,T11 22,TT 2T,T2 11 5 11111 1112,111T 1121,11T1 1211,1T11 2111,T111 122,1TT 212,T1T 221,TT1 12T,1T2 21T,T12 2T1,T21 21 6 " 43 7 " 85 8 " 171 N번째 방법의 수는 "2 * (N-2번째 방법의 수) + (N-1번째 방법의 수)" 와 같음을 알 수 있다. 소스코드 #include #define MOD 1..

풀이 입력받은 좌표들을 오름차순으로 정렬하고, 중복을 제거했을 때, 각 요소들이 몇 번째인지 출력하는 문제다. 입력받은 수들을 두 벡터에 저장하고, v2는 오름차순으로 정렬 후, 중복을 제거했다. 중복된 수가 제거된 v2에서 lower_bound()를 사용하면, 원하는 결과를 얻을 수 있다. 소스코드 #include #include #include using namespace std; int main(){ int N, temp; scanf("%d", &N); vector v1(N), v2(N); for (int i = 0; i < N; i++){ scanf("%d", &temp); v1[i] = v2[i] = temp; } sort(v2.begin(), v2.end()); v2.resize(unique(..

풀이 입력받은 시간을 오름차순으로 정렬 후, 기존의 대기시간(sum)과 i번째 사람이 인출하는데 걸리는 시간(arr[i])을 result에 누적 합으로 저장해주면 된다. 소스코드 #include #include int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); qsort(arr, N, sizeof(int), compare); int result = 0; for (int i = 0, sum = 0; i < N; result+=(sum+=arr[i++]))..

풀이 알고리즘은 엄청 간단하다. N명의 이름을 입력받아서 정렬 후, M명의 이름을 입력받아 이진탐색으로 찾은 명단과 총 인원을 출력하면 된다. 하지만, 이를 C로 구현하는 것은 끔찍하다... 소스코드 #include #include #include #include using namespace std; int main(){ int N, M, i; scanf("%d %d", &N, &M); vector v1(N), v2; char name[21]; for (i = 0; i < N; i++){ scanf("%s", name); v1[i] = name; } sort(v1.begin(), v1.end()); for (i = 0; i < M; i++) { scanf("%s", name); if (binary_sea..

풀이 DFS는 방문 기록이 없는 정점만 탐색하면 된다. BFS는 방문한 정점을 visited뿐만 아니라 Queue에 순서대로 기록하고, front로 탐색의 기준점을, rear로 탐색의 중단점을 설정해주면 된다. 소스코드 #include #include int N, arr[1001][1001], visited[1001], queue[1001]; void dfs(int v){ visited[v] = 1; printf("%d ", v); for (int i = 1; i

풀이 입력받은 N을 이용해 정사각형을 분할하면서 전부다 1 또는 0일때까지 탐색을 하면 된다. 소스코드 #include int paper[128][128], w, b; void color(int x, int y, int n){ int cnt = 0; for (int i = x; i < x+n; i++) for (int j = y; j < y+n; j++) paper[i][j] && cnt++; if (cnt == n*n)b++; else if (!cnt) w++; else { color(x, y, n/2); color(x, y+n/2, n/2); color(x+n/2, y, n/2); color(x+n/2, y+n/2, n/2); } } int main(){ int N; scanf("%d", &N); f..

풀이 숫자가 아닐 때까지 숫자로 변환해 temp에 저장하다가 부호를 만나면 sum에 저장했다. 처음에 숫자가 입력되므로 양수이기 때문에 '-'일 때, sub[0]에 저장을 해주고 sub[1] 이후로는 빼줄 수를 저장했다. 소스코드 #include #include #include int main() { char str[51]; scanf("%s", str); int len = strlen(str), sub[25] = {0,}, cnt = 0, sum = 0, temp = 0; for (int i = 0; i

풀이 입력받은 컴퓨터 쌍을 서로 접근할 수 있도록 반대 쌍 또한 값을 설정해주었다. 그리고, 이전에 접속한 컴퓨터에서의 탐색(중복)을 막기 위해 컴퓨터 번호에 해당하는 num배열의 값을 증가시켰다. 소스코드 #include int arr[100][100], num[100], N, cnt; void dfs(int worm){ cnt++, num[worm] = 1; for (int i = 0; i < N; i++) if (arr[worm][i] && !num[i]) dfs(i); return; } int main(){ int line, x, y; scanf("%d %d", &N, &line); for (int i = 0; i < line; i++){ scanf("%d %d", &x, &y); arr[x-1]..

풀이 편의를 위해 합 또한 2차원 배열로 저장을 해주었다. 다음은 문제의 예제로 주어진 표에 대한 누적 합을 저장한 배열 sum이다. [x, y]가 의미하는 바는 [1, 1] 부터 [x, y]까지의 누적 합이다. 만약, [2, 3](초록색), [4, 4](노랑색) 구간의 합을 구할 때, [2, 3]을 기준으로 불필요한 누적 합인 [1, 4](=10), [4, 2](=24)을 빼주면 된다. 하지만, [1, 4]와 [4, 2]를 빼는 과정에서 공통된 누적 합(분홍색)을 두번 빼므로, [1, 2]를 더해주어야 한다. 정리하면 다음과 같다. // input :: 4 4 2 3 sum[x2][y2]- sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] // ex) [4, 4] -..

풀이 구조체 배열의 index와 문자열을 이용해 숫자를 입력받을 떄는 별도의 탐색없이 출력이 가능하지만, 문자열 검색시에는 탐색을 필요로 하고, 이 과정에서 시간 초과가 발생해 map을 사용해 풀이했다. 소스코드 #include #include #include #include using namespace std; map name; map num; int main(){ int N, M; scanf("%d %d", &N, &M); char temp[21]; for (int i = 0; i < N; i++){ scanf("%s", temp); name[temp] = i; num[i] = temp; } for (int i = 0; i < M; i++){ scanf("%s", temp); if (temp[0]