0과 1의 쉼터

풀이 "백준 15652, N과 M (4)"를 참고해 풀이했다. 기존에는 1부터 입력받은 N까지의 수들 중에서 수열을 생성해야 했다. 이번에는 N개의 수를 이용해 수열을 생성하면 된다. 소스코드 #include #include int arr[8], N, M, num[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i num[i]) break; if (j == depth) arr[depth]..

풀이 "백준 15649, N과 M (1)"을 참고해서 풀이했다. 기존에는 1부터 입력받은 N까지의 수들 중에서 수열을 생성해야 했다. 이번에는 N개의 수를 이용해 수열을 생성하면 된다. 소스코드 #include #include int arr[8], N, M, num[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i < N; i++){ if (!depth) arr[0] = num[i]; else{ int j; for (j = 0; j < depth; j++) if (arr[j] == num[i]) break; if (j == depth) arr[dept..

풀이 "백준 15650, N과 M (2)"를 참고해서 풀이했다. 기존의 코드에 같은 수를 여러번 고를 수 있도록 수정만 하면 된다. for (j = 0; j i) break; // arr[j]에 담긴 수보다 작은 경우에만 저장하지 않는다. 소스코드 #include int arr[8], N, M; void BT(int depth){ for (int i = 1; i i) break; if (j == depth) arr[depth] = i; else continue; } if (depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ", arr[idx]); putchar(10); }else BT(depth ..

풀이 "백준 15649, N과 M (1)"를 참고해서 풀이했다. 이전 문제에서는 아래 코드와 같이 중복되는 수열을 거르기 위한 조건을 사용했다. for (j = 0; j = i) break; // arr[j]에 담긴 수보다 작거나 같을 경우 저장하지 않는다. 소스코드 #include int arr[8], N, M; void BT(int depth){ for (int..

풀이 편의를 위해 합 또한 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] -..

풀이 분할 정복을 이용한 거듭제곱 알고리즘의 기초적인 방법으로 풀이했다. 입력된 수는 int형으로 충분히 담아낼 수 있지만, 두 수의 곱은 이를 벗어나기 때문에, long long형으로 담아주어야 한다. Test Case에 주어지는 C의 값은 결과를 int형으로 출력할 수 있게 주어지는 듯 했다. 착한 문제지 쉬운 문제는 아니다. 홀수의 경우에는 A를 한번 더 곱해서 맞춰주어야 하므로 (B%2 ? A : 1) 으로 해결했다. 소스코드 #include long long mul(int A, int B, int C) { if (B > 1) { long long temp = mul(A, B/2, C); return ((temp*temp)%C * (B%2 ? A : 1)) % C; } else return A; ..

풀이 하나의 행에는 하나의 퀸만 존재한다는 점을 이용해, 배열의 index는 행, value는 퀸의 위치로 구현했다. nQueen() 0행 부터 Brute Force 방식으로 퀸이 놓일 수 있는지 확인하고, cnt값을 조작한다. put_check() 현재 행(index)의 value(퀸의 위치)가 다음 행의 value와 일치한다면, 동일한 열에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다. 현재 행(row)에서 이전 행(i)들을 뺀 값이 현재 행의 value(퀸의 위치)에서 이전 행의 value를 뺀 절대값과 동일하다면, 동일한 대각선 상에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다. 소스코드 #include #include int N, board[15], cnt; in..

풀이 출력 할 삼각형의 맨 위의 좌표(빨간 원)를 (0, N-1)이라고 하자. 이진트리 처럼 좌측 하단 삼각형의 맨 위 좌표(왼쪽 초록 원)는 (0 + N/2, N-1 - N/2), 우측 하단 삼각형의 맨 위 좌표(오른쪽 초록 원)는 (0 + N/2, N-1 + N/2)이다. 분할정복을 시행할 때마다, 입력받은 크기를 2로 나누어 건네주며, 전달받은 크기가 3이 될 때 배열에 빨간원 - 좌측 초록원 - 우측 초록원 이 순서대로 가장 작은 삼각형 내부에 별을 채워 넣는 것이다. 출력형식에 약간의 장난(?)이 숨어있다. 예제 출력을 드래그 해보니, 각 행의 마지막 별을 찍고 개행이 아니라, 공백을 출력해줘야 한다. memset()를 사용해 배열을 빠르게 초기화하고, 별을 채워 넣자. 소스코드 #include..