0과 1의 쉼터

풀이 난이도에 비해 조금 까다로운 문제이다. n을 포함하는 범위(min ~ max)를 알아낸 후, n을 포함하는 범위의 개수를 알아내야 한다. 소스코드 #include #include int compare (const void *a, const void *b){ int n1 = *(int*)a, n2 = *(int*)b; if (n1 n2) return 1; return 0; } int main(){ int L, n; scanf("%d", &L); int S[L]; for(int i = 0; i < L; i++) scanf("%d", &S[i]); scanf("%d", &n); qsort(S, L, sizeof(int), compare); int m..

풀이 키와 몸무게 둘다 큰 경우에만 cnt를 증가시켜준다. 소스코드 #include typedef struct{ int x, y; }Size; int main(){ int N; scanf("%d", &N); Size s[N]; for (int i = 0; i < N; i++) scanf("%d %d", &s[i].x, &s[i].y); for (int i = 0; i < N; i++){ int cnt = 0; for (int j = 0; j < N; j++) if (s[i].x < s[j].x && s[i].y < s[j].y) cnt++; printf("%d ", cnt + 1); } } 출처 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다...

풀이 '(', '[' 일때는 stack에 삽입해주고, ')', ']' 일때, top이 -1이 아니고, stack[top]에 '(', '['가 있을때, top를 감소한다. 만약 그렇지 않다면, "] ["나 ") (" 처럼 짝이 안맞는 경우이므로 출력을 위해 top값을 -2로 갱신하고 반복문을 빠져나온다. 소스코드 #include #define MAX 101 int main(){ char str[MAX], stack[MAX]; while (1){ gets(str); if (str[0] == '.') break; int top = -1; for (int i = 0; str[i] != '.'; i++){ if (str[i] == '(' || str[i] == '[') stack[++top] = str[i]; e..

풀이 입력받은 높이들 중에서 최대높이를 찾아 last로 지정하고, 절단기로 자를 나무의 높이(mid)를 기준으로 이분탐색을 사용해 풀이했다. mid보다 높은 높이의 나무만 자르며 필요한 M미터를 충족시킬때 result로 갱신해주었다. 소스코드 #include int arr[1000001]; int main(){ int N, M; long long last = 0; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++){ scanf("%d", &arr[i]); last < arr[i] && (last = arr[i]); } long long temp = 0, result = 0, first = 0, mid; while (first mid && (temp += (arr[..

풀이 최빈값을 구하는게 조금 까다로웠다. int mode = arr[0], cnt = 1, temp_cnt, temp; for (int i = 1; i cnt){ mode = arr[i]; temp_cnt = 0; }else if (temp_cnt == cnt) temp = arr[i]; if (arr[i] == mode) cnt++; else if (arr[i] != arr[i-1]) temp_cnt = 0; else temp_cnt++; } 이후 mode와 temp 중 큰 값을 출력하는 방식으로 Test Case 예제는 통과했으나, 결과는 틀린것으로 나왔다. 때문에 이번 문제는 평범하게 -4000 ~ 4000의 범위에 해당하는 배열을 이용해 풀이했다. -..

풀이 우선 Test Case를 입력받아 Queue에 저장하고, 최댓값을 찾았을 때의 index가 입력받은 M과 일치하기 전까지 최댓값을 제거하고, cnt를 증가시켜주는 방식으로 풀이했다. 소스코드 #include int main(){ int T, N, M; scanf("%d", &T); while (T--){ scanf("%d %d", &N, &M); int queue[N], idx = 0, cnt = 1; for (int i = 0; i < N; i++) scanf("%d", &queue[i]); while (1){ int max = 0; for (int j = 0; j < N; j++) max < queue[j] && (max = queue[j]); while (queue[idx] != max) id..

풀이 피보나치 수열과 같은 다음의 규칙이 존재한다. N 2진 수열 1 1 2 11 00 3 111 100 001 4 1111 0000 1100 1001 0011 5 11111 11100 11001 10011 00111 10000 00100 00001 Dynamic Programming 방식 중 Memoization 방식으로 풀이했다. 소스코드 #include int main(){ int N, dp[2] = {1, 2}, temp; scanf("%d", &N); if (N == 1){ printf("%d", 1); return 0; } for (int i = 3; i

풀이 "백준 1978 소수 찾기"문제와 유사하다. 단, 1은 소수가 아니다 arr[0] = 0으로 초기화해주자. 소스코드 #include #include #define MAX 1000000 int arr[MAX]; int main(){ int idx = 3; for (int i = 0; i < MAX; i++) arr[i] = i+1; for (int i = 2; i

풀이 다음과 같은 규칙이 존재한다. 둘째 줄부터 입력받은 수까지 push를 해주어야 하며, push는 이전에 입력된 수보다 큰 수가 입력될 때만 발생한다. push가 발생하거나, 이전에 입력된 수보다 작은 수가 입력될 경우 불필요해 생략한 후 pop가 발생해야한다. 만약, pop이 발생하지 않았다면, 스택을 이용해 수열을 만들 수 없다는 의미이다. 따라서, 둘째 줄부터 입력받는 n개의 수들을 저장할 필요가 없다. 소스코드 #include int main(){ int n; scanf("%d", &n); int stack[n], top = 0, val, idx = 0, num = 0; char op[2*n]; for (int i = 0; i < n; i++){ scanf("%d", &val); for (in..

풀이 "백준 11053 가장 긴 증가하는 부분 수열" 문제와 동일하다. 소스코드 #include int main(){ int N, max = 0, length; scanf("%d", &N); int arr[N], dp[N]; for (int i = 0; i < N; i++){ scanf("%d", &arr[i]); length = 0; for (int j = 0; j < i; j++) if (arr[j] < arr[i]) length < dp[j] && (length = dp[j]); dp[i] = length + 1; max < dp[i] && (max = dp[i]); } printf("%d", max); } 출처 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어..