본문 바로가기

백준

 (224)
백준 13458 - 시험 감독 www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 지문을 유의하여 보자. 총감독관은 오직 1명이고 부감독관은 여러명 있어도 된다고 한다. 예제 TC를 통해 해당 문장의 정확한 뜻을 유추해보자. 1 1 1 1 한개의 시험장에 한명이 시험볼 때 1을 출력할 것을 요구하고 있다. 즉 이 TC의 답 1은 무조건 들어가야 하는 총감독관을 의미하고 부감독관은 들어가지 않아도 상관없음을 알 수 있다. 이를 통해 총감..
[ICPC] 백준 9019 - DSLR www.acmicpc.net/problem/9019 주어진 명령어 D, S, L, R을 수행하여 초기 레지스터부터 목표 레지스터까지 최소 연산 횟수를 구하는 문제이다. 각 명령어 4개를 수행한 상태를 지금까지 연산한 횟수와 함께 큐에 넣어 목표 레지스터에 도달했을 때 최소 연산 횟수를 출력하면 된다. 시키는대로 BFS를 돌리면 되겠으나 문제는 L과 R인데 두 명령을 효율적으로 수행하지 않으면 TLE를 받게 된다. 작성자는 초기에 스트링으로 변환하여 옮기기, deque에다 각 자리 숫자를 넣어주기와 같은 방법을 시도하였으나 이는 전부 TLE를 받게 되고 아래와 같이 곱하기 나누기 연산을 통해 수를 바꿔주어야 제한 시간 내로 통과할 수 있다. // cur.first는 현재 레지스터이다. int l = cur..
[KOI] 백준 2638 - 치즈 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net KOI 중등부 치즈문제이다. 중등 치즈에서는 치즈 격자가 외부 공기와 두변 이상 접촉해야 녹는다고 하며 치즈를 모두 녹이는데 필요한 시간을 구해야 한다. 또한 모눈 종이에 가장자리에는 치즈가 놓이지 않는다는 조건이 있다. 이를 공기의 관점으로 접근하면 문제를 해결할 수 있다. 1. BFS로 공기를 흘려보낸다. 가장자리에는 치즈가 놓이지 않으므로 탐색 시작점은 (0, 0)이 적절할 것이다. 공간을 탐색하..
백준 1758 - 알바생 강호 www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수 www.acmicpc.net 고객이 기다리는 순번이 하나 증가할수록 주려는 팁에 패널티가 1씩 생길 때(역으로 돈을 갈취하지는 않는다.), 강호가 가장 많이 팁을 벌 수 있도록 하여 고객을 배치할 때 벌어들이는 팁을 구하는 문제이다. 높은 금액의 팁을 주는 고객일수록 적은 패널티를 받게 해야 최적해에 이를 수 있다. 따라서 팁을 많이 주는 순서대로 내림차순 정렬하여 받을 수 있는 팁을 계산하면 최적해를 구할 수 있다. ..
[ICPC] 백준 17521 - Byte Coin www.acmicpc.net/problem/17521 자본금으로 얼마나 많은 수익을 얻을 수 있을지 구하는 문제이다. 바이트 코인 예측 금액을 나열한 차트를 단조 감소하는 구간과 단조 증가 하는 구간으로 분리하여 단조 감소를 만족하는 마지막 날에 풀매수하고 단조 증가를 만족하는 마지막 날에 풀매도하면 최대 이익을 얻을 수 있다. 단조 감소 구간을 추적하는 L 포인터와 단조 증가 구간을 추적하는 R 포인터를 통해 최적 매수/매도 날짜를 탐색한 후 이를 계산하는 방식으로 구현했다. 전체 코드 더보기 #include using namespace std; using ll = long long; int main() { int days; ll seed; cin >> days >> seed; if (days == 1..

티스토리툴바