![]()
풀이 최소 금액 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/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 알고리즘 분류 수학 브루트포스 알고리즘 조합론 백트래킹 문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 ..
![]()
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. 만일, 확..
![]()
알고리즘 분류 구현 문자열 문제 동혁이는 NBA 농구 경기를 즐겨 본다. 동혁이는 골이 들어갈 때 마다 골이 들어간 시간과 팀을 적는 이상한 취미를 가지고 있다. 농구 경기는 정확히 48분동안 진행된다. 각 팀이 몇 분동안 이기고 있었는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 골이 들어간 횟수 N(10: t1=t1-(48*60-(60*m+s)) print('{:0>2}:{:0>2}'.format(t1//60,t1%60)) print('{:0>2}:{:0>2}'.format(t2//60,t2%60))
![]()
문제 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
![]()
문제 코드 arr = list(input().split()) arr1 = [] for i in arr: if i == 'i' or i == 'pa' or i == 'te' or i == 'ni' or i == 'niti' or i == 'a' or i == 'ali' or i == 'nego' or i == 'no' or i == 'ili': if i == arr[0]: arr1.append(i) else: continue else: arr1.append(i) ans = [] for i in range(len(arr2)): ans.append(arr1[i][0].upper()) print(''.join(ans)) 해설 입력되는 글자를 공백에 따라 arr이라는 리스트에 저장한다. 'i', 'pa', 'te..
![]()
문제 풀이 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) 코드 해석 ..
![]()
문제: 10773번: 제로 (acmicpc.net) 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 코드 코드 설명 위 문제는 스택을 이용하여 풀 수 있는 문제로, 스택에 저장할 정수가 0에서 1,000,000 사이의 값을 가지므로 long long형을 가지는 스택을 써주었다. 0이 입력이 된다면, 가장 최근에 입력된 수를 삭제해주는 처리를 해주면 되기 때문에, for문으로 반복하는 동안 0이 아닌 수가 입력이 되면 push를 이용해 스택에 쌓아 주었고 만약에 0이 입력이 되면..
