0과 1의 쉼터

풀이 입력받은 높이들 중에서 최대높이를 찾아 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[..

문제 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 입력 첫째 줄에 두 정수 min과 max가 주어진다. 출력 첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다. 제한 1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000 풀이 문제에서 주어진 "제곱 ㄴㄴ 수"는 수론에서 제곱 인수가 없는 정수(Square-free Integer)로, 1이 아닌 제곱수를 인수로 지 않는 양의 정수이다. 쉽게 정수에 대해 소인수분해를 했을 때 동일한 글에서..

풀이 최빈값을 구하는게 조금 까다로웠다. 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번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어..

풀이 입력받은 지점사이의 거리(y-x)는 다음과 같은 규칙성이 존재한다. 거리의 제곱근의 정수를 기준으로 구간이 나뉜다. (ex : 3.0 ~ 3.xx, 4.0 ~ 4.xx), 제곱근의 정수를 n이라고 한다. 거리가 n*n 일때 작동 횟수는 2n - 1번이다. (빨간색) 거리가 n*n보다 크고, n*n + n 이하일 때 작동 횟수는 2n번이다. (초록색) 거리가 n*n + n보다 크고, (n+1)*(n+1)미만 일 때 작동 횟수는 2n + 1번이다. (파랑색) 거리 작동 횟수 이동 기록 1 1 1 2 2 11 3 3 111 4 3 121 5 4 1211 6 4 1221 7 5 12211 8 5 12221 9 5 12321 10 6 123211 11 6 123221 12 6 123321 13 7 12332..

소스코드 #include int main(){ char ch; while (scanf("%c", &ch) != EOF) putchar(ch); } 출처 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net