전체 글

www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 아이디어: 투 포인트로 구현하면 되고, 대충 로직은 강의 들으면서 이해했는데 구현 과정에서 애를 먹었다. 이래서 어설프게 알면 안돼..ㅠㅠ left, right 포인터를 0, 0 으로 초기화하고 합result와 출력할 답 ans 도 0으로 초기화한다. 무한루프를 돌면서 합이 m보다 클 경우에는 합을 줄여야 하므로 result에서 arr[left]값을 빼고 left++한다..

www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아이디어: prefix sum(누적 합)을 이용하..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 아이디어: 이분 탐색으로 푼다는 게 무조건 mid 값을 찾는다는 게 아닌가보다..((아닐수도)) 1. 정렬 2. high = n-1, low = 0으로 포인터를 설정하고, while문을 수행하면서 특성값을 구하고 절댓값을 취하여 최솟값을 업데이트한다. 특성값이 음수면 low++(0에 가까워지려면 커져야 되니까), 양수면 high--(0에 가까워지려면 작아져야 되니까) impor..

www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 아이디어: 블루레이 크기를 이분 탐색. high = 10^9, low = 1 레슨의 길이를 더하다가 mid보다 같거나 커지면 블루레이 개수 +1 레슨의 길이가 M보다 크면 low = mid + 1, 같거나 작으면 블루레이 크기를 더 줄여야 하니까 high = mid - 1하고 ans 업데이트 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map..

www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 아이디어: 막대 과자의 길이를 이분 탐색하여 조카 n명에게 줄 수 있는 과자 길이의 최댓값을 구한다. import sys m, n = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) high = 1000000000 low =..

www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 아이디어: 시간을 이분탐색하여 시간의 최솟값을 찾는다. import sys n, m = map(int, sys.stdin.readline().split()) time = [] for _ in range(n): time.append(int(sys.stdin.readline())) high = 10**18 low = 1 ans = high while (high>=low): mid = (high+low..

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 아이디어: 이분 탐색의 기본 문제. 이분탐색의 로직을 잘 익히자. import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) arr.sort() m = int(sys.stdin.readline()) num = list(map(int, sys.stdin.read..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 아이디어: 배낭 문제 dp[i][k] = 최대 배낭 수용 무게가 k일때, i번째 까지의 물건을 봤을 때 가치의 최대합 i번째 물건을 넣을 수 있는 경우(k>=wi): max(dp[i-1][k-wi]+vi, dp[i-1][k]) i번째 물건을 넣을 때 vs 넣지 않을 때 가치가 더 큰 것 선택 i번째 물건을 넣을 수 없는 경우(k dp[n][k] ..

www.acmicpc.net/problem/14494 14494번: 다이나믹이 뭐예요? (1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=1e9+7)로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어: "오른쪽, 아래쪽으로만 움직일 수 있을 때, D[1][1]에서 D[x][y]까지 도달하는 경우의 수를 구하는 문제는 일일히 모든 경우를 다 계산할 필요 없이, D[i][j] = (i, j)에 도달하는 누적 경우의 수 = D[i-1][j] + D[i][j-1]를 세워서 해결할 수도 있죠." 문제에서는 →, ↓, ↘의 세 방향을 사용하므로 dp[i][j] = dp[i][j-1] + dp[i-1][j] +..

www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 제목이 이게 무슨 개소리야;; 왠지 좆같은데.. 한남 냄새가 나.. 아이디어: 1과 5로만 구성된 N자리 양의 정수 중, 15의 배수가 몇 개인지 15의 배수: 일의 자리는 0 or 5여야 하므로 일의 자리는 무조건 5, 각 자리의 합이 3의 배수여야 함. 5가 사용된 갯수 i에 따라 (1~N) 각 자릿수의 합을 구할 수 있음. -> 3의 배수인지 확인, 조합 이용(n-1Ci-1) import sys n = int(sys.stdin.readline()) ans = 0 #조합 구하기 N=n-1 dp =..