134. 주유소
원형 경로에 n개의 주유소가 있으며, i번째 주유소는 gas[i] 리터의 연료를 가지고 있습니다.
무한한 탱크 용량을 가진 자동차를 사용하여, i번째 주유소에서 i+1번째 주유소로 이동할 때 cost[i] 리터의 연료를 소모합니다. 하나의 주유소에서 출발하여 탱크가 비어 있는 상태에서 시작합니다.
두 정수 배열 gas와 cost가 주어졌을 때, 원형 경로를 한 바퀴 돌 수 있다면 ...
8월 16일 21:52에 게시됨
Codeforces Round 960 (Div. 2) 효율적인 문제 풀이 전략
A. Submission Bait (게임 이론)
앨리스와 밥이 $n$개의 원소를 가진 배열 $a$를 사용하여 게임을 진행합니다. 초기 mx 값은 0이며, 각 플레이어는 자신의 차례에 $a_i \ge mx$인 인덱스 $i$를 선택하여 mx를 $a_i$로 갱신하고 $a_i$를 0으로 만듭니다. 더 이상 움직일 수 없는 플레이어가 패배할 때, 앨리스의 필승 전략 존재 여부를 판별해야 합니다.
이 문제의 핵심은 ...
7월 30일 12:49에 게시됨
Codeforces Round #727 (Div. 2) A-D 문제 풀이
A. Contest Start (수학)
이 문제는 패턴을 분석하는 문제입니다. 참가자들의 시작 시간이 일정한 간격으로 배치될 때, 각 참가자가 기다려야 하는 평균 시간을 구해야 합니다.
먼저, 한 참가자가 끝날 때까지 기다리는 다른 참가자의 수를 생각해봅시다.
만약 한 참가자의 경기 시간이 \(t\)이고, 다음 참가자와의 시작 시간 차이가 \(x\)라면, 한 참가자가 경기하는 동 ...
7월 26일 14:19에 게시됨
Codeforces 라운드 920 (Div. 3) 문제 풀이 분석
이 문서는 Codeforces Round 920 (Div. 3)의 문제 D, E, F에 대한 해결 전략과 C++ 코드 예시를 제공합니다.
문제 D: 절댓값 합 최대화
문제 설명: 두 개의 배열 A와 B가 주어졌을 때, 각 배열에서 하나의 요소를 뽑아 쌍을 이루고, 이 과정에서 만들어지는 모든 쌍의 요소들의 절댓값 차이의 합을 최대화해야 합니다. 모든 요소는 단 한 번만 사용될 수 있습니다.
해결 ...
7월 26일 06:22에 게시됨
CF987 문제 분석 및 해결 전략
A번 문제: 최대 반복 수 유지하기
수열이 감소에서 증가로 변하는 경우, 중간에 연속된 동일한 값의 구간은 변경되지 않으며, 그 앞과 뒤는 반드시 변경되어야 한다. 왜냐하면 어떤 원소의 앞쪽 원소들은 기존에는 자신보다 크거나 같아야 했지만, 변화 후에는 작거나 같아야 하며, 뒤쪽 원소들 역시 반대로 작거나 같았던 것이 크거나 같아져야 하기 때문이다. 따라서 같 ...
7월 24일 16:44에 게시됨
ICPC Asia EC Regionals 2024 온라인 예선 (II) 풀이
A - 지역 예선 선택 도박
문제 요약
총 $k$개의 경기가 있으며, 각 경기마다 대학당 최대 $c_i$개 팀이 참가 가능하다. $n$개 팀이 있고 각 팀은 점수와 소속 대학 정보를 가진다. 각 팀은 최대 2개 경기에 출전할 수 있다. 모든 팀이 최악의 상황에서 얻을 수 있는 최선의 순위를 구해야 한다.
핵심 아이디어
최악의 경우는 내가 참가하는 경기에 강팀들이 몰리는 상황이 ...
7월 23일 20:16에 게시됨
COCI 2014-2015 #6 PAPRIKA 고추 문제
문제 설명
주厨 Marin은 n개의 고추를 가지고 요리를 만들 예정이다.
그는 나이가 x일 이하인 모든 고추로 요리 A를 만들고, 나머지 모든 고추로 요리 B를 만든다.
각 고추는 자신의 꿈을 가지고 있으며, 자신이 요리 A가 되고 싶은지 요리 B가 되고 싶은지 알고 있다.
하지만 고추들은 x의 값을 모른다. 꿈을 실현하는 고추의 수를 최대화하기 위해 다음과 같은 교환 ...
7월 16일 19:29에 게시됨
LeetCode 알고리즘 문제 분석: 이분 탐색을 이용한 최적해 도출 기법
문제 1: 일별 최대 작업 시간 최소화 (LCP 12)
특정 프로젝트 진행 시 전체 작업량을 $N$개의 과제들로 나누어 $M$일 동안 처리해야 하는 상황을 가정합니다. 각 과제에는 고유한 수행 시간이 존재하며, 반드시 순서대로 실행되어야 합니다. 다만, 매일 한 번씩 전문가의 도움을 받아 특정 과제의 소요 시간을 제로로 할 수 있는 기회가 주어집니다. 이 조건 하에서 $M$일 ...
7월 7일 04:35에 게시됨
Codeforces Edu Round 143 A-B 풀이 정리
A번: Two Towers
빨간색(R)과 파란색(B) 블록으로 구성된 두 개의 탑이 주어진다. 한 번의 이동에서는 길이가 2 이상인 탑의 꼭대기 블록을 다른 탑으로 옮길 수 있다. 이동을 통해 두 탑 모두 빨강-파랑이 번갈아 나타나는 형태로 만들 수 있는지 판별하는 문제다.
핵심 관찰
탑의 구조를 분석하면 몇 가지 중요한 사실을 발견할 수 있다:
각 탑 내부에서 인접한 동일 색 ...
7월 5일 00:34에 게시됨
NOIP 연습 세션 #1 상세 문제 풀이
문제 A: 점 쌍의 각도 최적화
이 문제는 두 점 사이의 관계를 최적화하는 전형적인 그리디 알고리즘 문제입니다. 데이터 범위를 고려했을 때 $O(n \log n)$ 시간 복잡도가 필요하며, 정렬을 활용해야 합니다.
핵심 아이디어는 좌표축을 45도 회전시키는 것입니다. 기존 좌표 $(x, y)$를 $(x+y, x-y)$로 변환하면, $y=x$ 또는 $y=-x$에 가장 가까운 값을 찾는 문제가 됩니 ...
6월 28일 01:33에 게시됨