![]()
https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 문제 분석 시뮬레이션 문제처럼 보이기도 하지만, 조금 고민해보면 실시간으로 고객들이 계산대로 이동했다가 출구로 빠져나가는 것이 아니므로 우선순위 큐를 이용하면 문제를 쉽게 해결할 수 있다는 것을 알 수 있습니다. 차근차근 어디서 어떻게 우선순위 큐를 사용해야 할지 생각해봅시다. 문제 풀이 우선은 계산대를 우선순위 큐로 만들어야 할 것 같습니다. 이 우선순위 큐의 규..
https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제분석 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기..
![]()
6236번: 용돈 관리 (acmicpc.net) 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 해석 M번 인출하여 주어진 이용할 금액을 만족하는 K원 중 최소값을 구하는 문제이다. 만약 돈이 남을 경우, 남은 금액을 모두 넣고 다시 K원을 인출해야하므로 즉 하루 이용금액보다 K원이 작으면 안된다. 코드 문제 풀이 이분탐색을 활용하였다. 하루 이용금액은 arr에 저장해주었고 left는 0, right는 1000000000로 지정해주었다. while문안을 살펴보면 중간값을 mid로 지정해주었고 이 mid는 하루..
![]()
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 문제분석 분류 누적 합 문제설명 R x C 크기의 사진이 주어질 때, 사진의 일부분에 해당하는 밝기 평균을 구한다. 입력: 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C(1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q(1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R x C 크기의..
![]()
Intro Solution 주어진 문자열에 특정한 알파벳이 몇 개 들어있는지 구하는 문제다. 질문이 최대 200,000개 주어지며 알파벳이 중복으로 주어질 수 있기 때문에 누적 합을 이용해서 시간복잡도를 줄여야 한다. 주어진 질문의 알파벳이 처음 나왔다면, 문자열을 순회하며 해당 문자열 개수의 누적 합을 저장한다. python으로 실행할 때 제한 시간을 통과하지 못했으나, pypy3으로는 통과할 수 있었다. Code import sys input = sys.stdin.readline def solve(): S = input().strip() size = len(S) q = int(input()) psum = {} for _ in range(q): a, l, r = input().split() l, r =..
![]()
https://www.acmicpc.net/problem/2315 2315번: 가로등 끄기 첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가 www.acmicpc.net 문제 문제 유형 다이나믹 프로그래밍, 누적 합 문제 분석 실력과 기술이 좋지않으면 잡무나 평생하게 된다는 철학을 담은 문제다. 마징가z가 특정 위치(가로등) 에서 시작하고, 모든 가로등을 끌 때 까지 소모되는 전력양을 구하는 문제이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..
![]()
https://www.acmicpc.net/problem/2435 2435번: 기상청 인턴 신현수 첫째 줄에 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 주어진다. N은 온도를 측정한 전체 날짜의 수이다. N은 2이상, 100이하이다. K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사 www.acmicpc.net 문제 분석 N개의 정수를 입력 받아서 연속되는 K개의 수의 합이 최대가 되는 값을 구하는 문제이다. 누적합을 사용해야 시간 제한을 어기지 않을 수 있다. 코드 #include #include using namespace std; int main(){ int n, k; cin>>n>>k; int sum[n+1]; sum[0] = 0; int tmp; for(int i=1;..
![]()
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제분석 분류 구간합(Prefix sum) 다이나믹 프로그래밍(Dynamic Programming) 문제설명 배열의 크기 N 입력 구간합 구하는 횟수 M 입력 배열 입력, 구간합 좌표 입력 입력된 좌표 (시작X, 시작Y) (종료X, 종료Y) 사이의 구간을 입력 구간합 -> O(N)의 속도로 문제 도출 입력 4 3 1 2 3 4 2 3 4 5 3 4 5 6..
![]()
https://www.acmicpc.net/problem/14627 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 www.acmicpc.net [문제 해석] 이 문제는 이분 탐색 문제로, 최소값과 최대값을 고려하면서 적절한 값을 찾아가는 문제이다. 이 문제에서 주의할 점은 라면에 넣을 파의 양이라는 점이다. [소스코드] S, C = map(int, input().split()) pa = [] for _ in range(S) : pa.append(int(input())) start, end =..
![]()
https://www.acmicpc.net/problem/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 문제 분석 배열에서 일정 범위 a~b에 정수 k를 더하는 명령을 여러 번 수행하는 문제입니다. 단순히 매 명령마다 배열에서 a~b까지 k를 더하도록 구현하면 시간복잡도가 O(NM)이 되어 시간 안에 문제를 풀 수 없습니다. 더 좋은 방법은, 명령의 범위 a, b와 더할 숫자 k를 기록하는 배열을 만들고, 누적합을 이용하여 원래 배열에 더해주는 것입니다. 이렇게 구현하면 시간복잡도는 ..
![]()
백준 1644 소수의 연속합 Intro Solution 입력되는 수보다 작은 소수들을 합하여 입력된 수를 만들어야 하고, 해당 소수들은 연속된다. 먼저 에라토스테네스의 체를 이용하여 입력 이하의 소수의 목록을 만든다. 소수 목록의 누적 합 리스트를 만든다. 투 포인터(l, r)를 이용해 포인터를 뒤로 옮겨가며 답을 구한다. 3.1. 포인터 l부터 포인터 r까지의 소수의 합이 n과 동일할 때 정답으로 출력할 변수에 1을 더한다. 3.2. 소수의 합이 n보다 작으면 오른쪽 포인터를 한 칸 이동한다. 3.3. 소수의 합이 n보다 크거나 같으면 왼쪽 포인터를 한 칸 이동한다. Code def primes(n): # 에라토스테네스의 체 if n < 2: return [0] is_prime = [True] * (n..
![]()
14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 해석 NxM 크기의 직사각형 안에 있는 로봇청소기가 청소한 칸의 개수를 구하는 문제이다. 청소기는 특정 알고리즘에 따라 움직이므로 해당 알고리즘을 그대로 구현하여 시뮬레이션 해야한다. 코드 문제 풀이 처음 변수 선언 부분부터 설명하자면 arr는 NxM의 직사각형이 들어갈 list이고 0은 빈칸, 1은 벽, 2는 이미 청소한 칸을 나타낸다. flag는 로봇청소기가 해야할 알고리즘 단계를 나타내며 0은 문제의..
