0과 1의 쉼터

풀이 정렬된 점수들의 절사평균을 구하는 문제이다. 가장 작은 15%의 인원과, 가장 큰 15%의 인원을 제외한 후 나머지 인원에 대해 평균을 구한 후 반올림을 해서 출력해주면 된다. 문제는 단순하지만 Python을 사용하다보니 예상치 못한 복병들이 많았다. 우선 첫 번째로 주어지는 점수들의 개수가 최대 3 x 10^5 이다. 실버 난이도의 문제답지 않게 많은 입력이 주어진다. 빠른 입출력을 해주자. 그 다음으로는 전체 인원에 대한 절사평균이 성립하지 않는 경우다. 즉, 인원이 너무 적어 절사평균을 구하기 위해 제외해야할 인원이 적은 경우이다. 15%에 해당하는 인원의 반올림한 값이 0보다 큰 경우에만 인원을 제외시켜 주자. 다른 하나는 Python의 round()의 작동 방식에 대한 문제다. 일반적으로 ..

풀이 스택이란 항아리 처럼 나중에 집어넣은 것이 먼저 나오는 제한적 접근 나열 구조이다. LIFO(Last In First Out) 형식이며, 기본 개념을 구현만하면 된다. 단, 한 줄에 하나씩 출력해야 한다는 것을 명심하자 pop 명령을 실행하기 전에 스택이 비었는지 확인하기 위해 empty 명령어만 함수로 구현했다. 실제 메모리에 대한 참조를 해제할 필요 없이, 변수 top을 사용해 값을 가르키는데 제한을 두었다. 소스코드 소스코드 보기 출처 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net..

풀이 최대 100개의 카드 중에서 3장의 카드를 고를 수 있는 모든 경우의 수를 탐색해도 제한 시간 내 합을 출력할 수 있다. 3개의 카드를 골라야 하니 3중 loop을 사용해 탐색하자. loop의 조건이 순서대로 1씩 감소하는 이유는, 최악의 경우 중복된 카드를 뽑지 않고서는 N - 2 ~ N 번째 카드를 선택했을 때가 조건에 맞는 최댓값이 나오는 경우이기 때문이다. 소스코드 소스코드 보기 출처 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net

풀이 C(N, K)에 대해 N의 범위는 1 ~ 10, K의 범위는 0 ~ N이므로 단순 계산으로 풀이할 수 있다. C(N, K) = N! / (K! * (N - K)! N! = N * (N - 1) * (N - 2) * ... * 1 (N - K) ! = (N - K) * (N - K - 1) * (N - K - 2 ) * ... * 1 이때, N의 sub factorial과 K! 을 구해서 나누어주면 곱셈 횟수를 줄일 수 있다. ex) N = 5, K = 2 5 4 3 2 1 2 1 3 2 1 소스코드 소스코드 보기 출처 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net

풀이 256 ~ 0까지 모든 높이의 평지를 만들어보며 최단 시간을 구하는 문제이다. 동일한 층의 개수를 배열로 입력받았고, 가장 높은 층을 구했다. 최단시간이 동일하다면, 높이가 가장 높은 것을 출력해야 하기 때문에 256부터 0으로 내려가면서 탐색했다. (만약 시간이 동일하다면 높은 층의 기록이 유지되므로) 최대 시간(result)은 다음과 같다. 땅의 크기(500 x 500) x 설치(2) x 최대높이(256) = 128,000,000 소스코드 #include int main(){ int N, M, B, arr[257] = {0, }, temp, max = 0; scanf("%d %d %d", &N, &M, &B); for (int i = 0; i < N*M; i++){ scanf("%d", &tem..

풀이 0을 입력받으면 pop, 아니면 push이다. 연산 효율을 위해 일단 입력받고 0이면 top를 -2만큼 감소시켰다. 소스코드 #include int main(){ int K; scanf("%d", &K); int stack[K], top = -1, sum = 0; for (int i = 0; i < K; i++){ scanf("%d", &stack[++top]); if (!stack[top]) top -= 2; } for (int i = 0; i

풀이 키와 몸무게 둘다 큰 경우에만 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의 범위에 해당하는 배열을 이용해 풀이했다. -..