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++]))..

풀이 별을 아래의 그림처럼 노란색, 연두색, 하늘색으로 나누어 찍었다. if (abs(j) >= N-1 && abs(i) == N-1) putchar('*'); // 노란색 else putchar((abs(j)-abs(i) == N-1) || (abs(i)==abs(j)) ? '*' : 32); // 연두색 || 하늘색 마지막 별을 찍고 개행을 해야 한다는 점을 유의하자. 소스코드 #include #include int main(){ int N; scanf("%d", &N); for (int i = -N+1; i = N-1 && abs(i) == N-1) putchar('*'); else ..

풀이 별을 아래의 그림처럼 노란색, 연두색, 하늘색, 분홍색으로 나누어 찍었다. void mark_star(int p, int N){ if (N == 1) arr[p][p] = arr[p+1][p] = arr[p+2][p] = '*'; // 노란색 else { int row = 4*N-1, col = row-2; for (int i = p; i < p+col; i++) arr[p][i] = arr[p+row-1][i] = '*'; // 연두색 for (int i = p+2; i < p+row-1; i++) arr[i][p] = arr[i][p+col-1] = '*'; // 하늘색 arr[p+1][p] = arr[p+2][p+col-2] = '*'; // 분홍색 mark_star(p+2, N-1); } }..

소스코드 #include int main(){ int N; scanf("%d", &N); for (int i = 0; i < 2*N; i++){ for (int j = 0; j < N; j++) putchar((i+j)%2 ? 32 : '*'); putchar(10); } } 출처 10996번: 별 찍기 - 21 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net

소스코드 #include #include int main(){ int N; scanf("%d", &N); for (int i = -2*N+2; i < 2*N-1; i++){ for (int j = -2*N+2; j < 2*N-1; j++){ if (i%2==0 && abs(j)

소스코드 #include int main(){ int N; scanf("%d", &N); for (int i = 0; i < N; i++){ for (int j = 0; j < 2*N; j++) putchar((i+j)%2 ? 32 : '*'); putchar(10); } } 출처 10995번: 별 찍기 - 20 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net

풀이 Mobius function와 Mertens function로 풀이했다. 편의상 "제곱ㄴㄴ수"는 SFI(Square Free Integer, 제곱 인수가 없는 정수)라고 부르겠다. Mobius function Mobius function은 다음의 조건에 따라 값을 반환하는 함수다. 제곱 인수가 없을 때, 소인수의 개수가 홀수이면 1 제곱 인수가 없을 때, 소인수의 개수가 홀수이면 -1 제곱 인수가 있는 정수이면 0 Mertens function Mertens function는 Mobius function의 부분합으로, 입력받은 수 까지 존재하는 SFI의 개수를 알 수 있다. K의 최댓값 즉, 1,000,000,000번째 SFI를 구하기 위해서는 Mobius function의 반환값들을 얼마나 저장해..

풀이 알고리즘은 엄청 간단하다. 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..