![]()
풀이 최소 금액 K의 범위를 생각해봅시다. K는 각 날짜마다 필요한 금액보다는 크거나 같아야 합니다. 즉, K는 1부터 N * 최대 사용 금액 사이의 값일 수 있다. 이분 탐색을 이용하여 가능한 K 값을 찾습니다. 이때, 이분 탐색의 중간값(mid)을 사용하여 K를 검사한다. 주어진 N일 동안 각 날짜별로 사용할 금액을 순회하면서 현재 인출 가능한 금액(mid)로 사용할 수 있는지 확인한다. 만약 mid로 사용할 수 없는 날이 나온다면, 인출 횟수를 늘려야한다. 만약 인출 횟수가 M 이하라면, 가능한 K값 중 작은 범위에서 다시 탐색. 그렇지 않다면, K값을 더 큰 범위에서 탐색한다. 위를 반복하여 최소금액 K를 찾으면 된다. 코드 #include #include #include using namespa..
![]()
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net N개의 정수가 있는 집합 A, M개의 정수가 있는 집합 B 존재 -> B의 요소들이 A에 포함되는지 확인 - 이분탐색 1. 집합 N 정렬 2. 시작과 끝 지점의 인덱스 지정 3. 시작 + 끝 // 2 구하기 4. 중간 지점의 값과 해당 값 비교 -> 동일하면 찾은 것 / 값이 크면 윗부분 탐색 / 값이 작으면 아랫부분 탐색 => 반복 5. 만일, 확..
![]()
문제 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 누적 합을 저장하기 위해 새로운 2차원 배열(ps)을 만들어 준다. 이중 반복문을 이용하여 누적합을 저장한다. ps[i][j] = ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1] + li[i-1][j-1] 입력받은 좌표에 해당하는 밝기의 합을 구한다. ps[x2][y2] - ps[x2][y1-1] - ps[x1-1][..
https://www.acmicpc.net/problem/23827 23827번: 수열 (Easy) 모든 원소가 양의 정수이고, 길이가 $N$인 수열 $A_1, A_2, ..., A_N$이 주어진다. $1 \le i < j \le N$을 만족하는 모든 정수쌍 $(i, j)$에 대해 $A_i \times A_j$의 합을 $1\, 000 \, 000 \, 007$로 나눈 나머지를 구하시 www.acmicpc.net # 문제 설명 - 모든 원소가 양의 정수이고, 길이가 N인 수열 A1, A2, ... , AN이 주어진다. 1
Problem https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net Code import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) m = int(input()) prefix_sum=0 for i in arr: prefix_sum+=i if prefix_sum
![]()
문제 풀이 2차원 배열의 누적 합을 구하는 문제다. 입력을 받으면서 누적 합을 만들었고, i 또는 j의 인덱스가 0인 곳엔 0을 채워 넣었다. 큰 네모(arr[x2][y2]에서 가장자리에 해당하는 두 네모(arr[x2][y1 - 1], arr[x1 - 1][y2])를 빼주고, 작은 네모(arr[x1 - 1][y1 - 1]는 두번 빠졌기에 한번 더해줬다. 코드 #include #include using namespace std; int N, M; int arr[1025][1025]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 표의 크기 N, 합을 구하는 횟수 M cin >> N >> M; // 입력 & 누..
https://www.acmicpc.net/problem/16713 16713번: Generic Queries 첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$) 둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$) 그 후, $Q$개의 줄에 걸 www.acmicpc.net 1. 문제풀이 누적합 문제를 XOR 연산을 적용하여 만든 문제이다. XOR 연산은 교환법칙과 결합법칙이 성립한다. 양수 A가 있을 때 XOR 연산은 다음이 성립한다. 1. A XOR 0 = A (0은 항등원) 2. A XOR A = 0 (A는 역원) 위 식이 성립할 때, ..
16401번: 과자 나눠주기 (acmicpc.net) 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 문제 코드 m,n=map(int,input().split()) l=sorted(list(map(int,input().split()))) if m> sum(l): x=0 else: left=1 right=l[-1] while left=m: x=mid left=mid+1 else: right=mid-1 print(x) 코드 해석 ..
![]()
Problem Solution N과 M을 입력 받고 N개의 정수로 이루어진 수열 A를 입력 받는다. 누적 합 배열인 prefixSum을 초기화 하고 두 개의 반복문을 사용해 모든 부분합을 구한다. 첫 번째 반복문에서는 구간의 시작 위치 start를 1부터 N까지 순회한다. 두 번째 반복문에서는 구간의 끝 위치 end를 start부터 N까지 순회한다. 모든 가능한 구간 합을 확인한 후 누적 합 배열을 이용하여 구간 합을 계산 한다. prefixSum[end] - prefixSum[start - 1]을 통해 수열 A의 start부터 end까지의 합을 구하고 이 합이 M과 같다면 경우의 수를 증가시킨다. 모든 구간에 대해 경우의 수를 구하고 이를 출력한다. Answer #include #include usin..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답코드 # 숫자 카드 # 복습 횟수:2, 00:10:00, 복습필요X import sys si = sys.stdin.readline N = int(si()) own_list = list(map(int, si().split())) own_list.sort() M = int(si()) check_card_list = list(map(int , si().split()))..
https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 입력으로 주어지는 행 또는 열의 크기 N은 10^5 , 따라서 전체 행렬의 크기는 최대 10^10 으로, 10,000,000,000 (100억)이 된다. 이는 브루트-포스로 탐색하기에는 너무 오래걸린다는 뜻이다. 그러나 사실 위의 조건만 가지고 이 문제를 이분탐색 문제라고 생각하기는 어렵다. 문제에서 A와 B배열의 인덱스는 1부터 시작하는데, 예를 들어 B[7]=6이..
![]()
문제 https://www.acmicpc.net/problem/27278 27278번: 영내순환버스 첫 번째 줄에 승하차 지점 수 $N$과 병사 수 $M$이 공백으로 구분되어 주어진다. $(2 \leq N \leq 100\,000;$ $1 \leq M \leq 100\,000)$ 두 번째 줄에 $i$번 지점에서 $i+1$번 지점으로 갈 때 걸리는 시간 $t_i$가 공 www.acmicpc.net Algorithm 운전병이 운전 업무를 마친 시간을 구하라고 했으므로 가장 마지막에 내린 병사가 언제내렸는지를 구하면 되는 문제이다. 문제에서 주어지는 거는 각 정류장 사이의 거리와 병사가 출발정거장에서 기다리기 시작한 시간이다. 그러면 우리가 따져주어야 하는 것은 다음과 같다. 병사가 탑승한 시간 병사가 내린 ..
